Java玩转《啊哈算法》解密QQ号之队列

行有不得,反求诸己

开头

各位好!本人在看《啊哈算法》,写的确实不错。

但略微遗憾的是,书籍示例代码是c语言,不是本人常用的java

那就弥补遗憾,说干就干,把这本书的示例语言用java过一遍, 顺便附上自己的一些理解!

于是就有了本篇博客,本篇博客主要是讲常见数据结构的一种:队列。

来不及买纸质书但又想尽快感受算法魅力的童鞋也甭担心,电子版的下载链接已经放到下方了,可尽情下载。

链接:https://pan.baidu.***/s/1imxiEl***orw2F-HJEnB-PA?pwd=jmgs
提取码:jmgs

代码地址

本文代码已开源:

git clone https://gitee.***/guqueyue/my-blog-demo.git

请切换到gitee分支,

然后查看aHaAlgorithm模块下的src/main/java/***/guqueyue/aHaAlgorithm/chapter_2_StackAndChainTable即可!

引子

案例

在书中,作者直接给出了一个案例来引出队列这个概念:

新学期开始了,小哈是小哼的新同桌(小哈是个小美女哦~),小哼向小哈询问QQ号,小哈当然不会直接告诉小哼啦,原因嘛你懂的。所以小哈给了小哼一串加密过的数字,同时小哈也告诉了小哼解密规则。

规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,再将第5个数删除……直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一起就是小哈的QQ啦

现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。

分析

那么,如何通过抽象化的编程来解决这个具体化的问题呢?

其实很简单,只需要三步即可!!!

  1. 首先,我们需要声明一个数组用来存储QQ号,这里其实我们就是用数组来模拟队列。
  2. 其次,我们要运用双指针的思想,声明一个头指针和一个尾指针。头指针指向队列头部,尾指针指向队列尾部后一位。
  3. 然后,我们只需要一直执行第一个元素出队并打印,下一个元素出队并入队的操作,直至两个指针相遇即队列为空便可。

下面是整体的流程图:

代码

根据上文的分析,我们不难编写出以下代码:

package ***.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;

/**
 * @Author: guqueyue
 * @Description: 解密QQ - 本质是以数组模拟队列
 * @Date: 2024/1/11
 **/
public class DecodeQQ {
    public static void main(String[] args) {

        // 加密过的qq号
        int[] qq = {6, 3, 1, 7, 5, 8, 9, 2, 4};

        // 创建一个长度为101的队列
        int[] queue = new int[101];
        // 初始化队列:头指针head指向队列头部,尾指针tail指向队列尾部后一位
        int head = 0, tail = 0;

        // 初始化队列:tail为尾指针,指向队列尾部后一位
        for (int num : qq) {
            queue[tail++] = num;
        }

        // 破解qq号
        while (head < tail) { // 队列不能为空

            // 打印队首并出队
            System.out.print(queue[head++] + " ");

            // 将队首的数字放到队尾
            queue[tail++] = queue[head++];
        }
        System.out.println();
    }
}

运行代码,可得:

队列

在上文中,我们看似用的是 数组双指针的方法,其实我们运用的是队列的思想。

当然,用链表也能实现栈,这里我们就不讲了。

队列,顾名思义,就是跟排队一样,先到的人先买票,后到的人后买票

也就是说,队列只有两种操作:

  1. 队首的人出队
  2. 新来的人入队

这里面有一个非常重要的核心概念 - FIFO(First In First Out) - 先进先出

与之对应的我们后面要讲到的栈,它是先进后出。队列和栈可以说是算法里面比较核心的两种数据结构了,不容小视。

封装

为了方便使用,减少重复性代码,我们可以专门封装一个队列类:

package ***.guqueyue.aHaAlgorithm.entity;

/**
 * @Author: guqueyue
 * @Description: 队列类 - 通过数组实现
 * @Date: 2024/1/11
 **/
public class Queue {

    public int[] data = new int[1001]; // 数组,用来储存内容
    public int head; // 队首
    public int tail; // 队尾

    @Override
    public String toString() {
        String str = "";

        int head = this.head, tail = this.tail;
        while (head < tail) {
            str += data[head++] + " ";
        }
        str += "\n";

        return str;
    }
}

这里主要有三个核心:

  1. 用来存储元素的数组
  2. 队首指针
  3. 队尾指针

    然后,跟原书不同的是:为了方便输出队列元素,我们还重写了队列类的toString()方法。

这样的话,我们使用队列,只需要创建一个队列对象。

出队只需要将队首指针+1,入队只需要根据队尾指针进行赋值操作,然后再将队尾指针+1即可。

如下代码,我们创建一个队列,将元素3入队,再出队为:

   Queue queue = new Queue(); // 创建队列
   queue.data[queue.tail++] = 3; // 将3入队
   queue.head++; // 再将3出队

升级

我们运用队列封装类,可以给上文的案例代码进行如下改装:

package ***.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;

import ***.guqueyue.aHaAlgorithm.entity.Queue;

import java.util.Scanner;

/**
 * @Author: guqueyue
 * @Description: 队列演示
 * @Date: 2024/1/11
 **/
public class QueueTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("你要输入几个数?:");
        int n = scanner.nextInt();

        // 初始化队列
        Queue queue = new Queue();
        System.out.printf("清输入%d个数,中间用空格隔开,再回车:", n);
        for (int i = 0; i < n; i++) {
            queue.data[queue.tail++] = scanner.nextInt();
        }

        System.out.print("解密后的qq号为:");
        while (queue.head < queue.tail) { // 队列不为空,则循环

            // 打印队首并出队
            System.out.print(queue.data[queue.head++] + " ");

            // 将队首移到队尾
            queue.data[queue.tail++] = queue.data[queue.head++];
        }
        System.out.println(); // 换行
    }
}

演示

运行代码,控制台输入,可得:

最后,放一段作者的吐槽:

队列的起源已经无法追溯。在还没有数字计算机之前,数学应用中就已经有对队列的记载了。
我们生活中队列的例子也比比皆是,比如排队买票,又或者吃饭时候用来排队等候的叫号机,又或者拨打银行客服选择人工服务时,每次都会被提示“客服人员正忙,请耐心等待”,因为客服人员太少了,拨打电话的客户需要按照打进的时间顺序进行等候等等。
这里表扬一下肯德基的宅急送,没有做广告的嫌疑啊,每次一打就通,基本不需要等待。
但是我每次打银行的客服(具体是哪家银行就不点名了)基本都要等待很长时间,总是告诉我“正在转接,请稍候”,嘟嘟嘟三声
后就变成“客服正忙,请耐心等待!”然后就给我放很难听的曲子。看来钱在谁那里谁就是老大啊……

转载请说明出处内容投诉
CSS教程_站长资源网 » Java玩转《啊哈算法》解密QQ号之队列

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买