思路分析
上一讲我们讲过,队列既可以用数组来实现,也可以用链表来实现,但由于我们比较熟悉数组这种结构,所以这里我会先给大家讲一下数组这种实现方式,至于链表这种实现方式,那就以后有机会再说吧!
队列,它本身就是一个有序列表,且其若是使用数组这种结构来存储它里面的数据的话,则队列数组的声明就应该是如下图所示的这个样子,其中maxSize就是该队列的最大容量。
上面这张示意图,大家应该还有些印象吧,你可千万别跟我说不熟悉啊,因为我上一讲就已经给大家讲过了。
我不知道大家是否能从以上示意图中看出这一点,就是在使用数组模拟队列时,我们应该是要创建这样一个类的,即:
class ArrayQueue { private int[] arr; // 该数组是专门用于存放数据的 private int maxSize; // 表示数组的最大容量 private int front; // 表示队列的头指针 private int rear; // 表示队列的尾指针 ......}
不难发现,ArrayQueue类中是必须要有以下这四个成员属性(或者成员变量)的:
- private int[] arr:由于是使用数组来模拟队列,所以在设计队列时它内部必然是要有一个数组来专门用于存放数据的;
- private int maxSize:它表示的就是数组的最大容量;
- private int front/rear:由于队列的输入、输出是分别从前后端来处理的,所以我们需要两个变量front及rear来分别记录队列前后端的下标,当然,不用说想必大家也都知道了,front会随着数据的输出而改变,而rear则会随着数据的输入而改变。
接着我们来继续分析一下队列里面常用的那几个操作。
其实,傻傻地思考一下,你就应该知道队列里面那几个常用的操作必然是少不了下面这五个的,即:
- 创建队列;
- 将数据存入队列;
- 从队列中取数据;
- 判断队列是否已满;
- 判断队列是否为空。
当然,肯定还有其他操作,只是这些操作我们目前还一时半会想不起来,不过这也没什么的,等到咱们用代码实现过后,你就什么都一清二楚了。
接下来,我啥也不说了,直接来给大家分析一下我们是如何将数据存入队列的。
既然是要将数据存入队列,那么必然是要有一个对应的成员方法来完成该操作的,不妨我们就称呼该方法为addQueue,很显然,该方法的处理必须包含如下两个步骤:
-
尾指针得往后移一位,即rear + 1。
为啥得这样做呢?因为我们在往队列里面添加数据时得从队列的尾部开始添加。
-
若尾指针rear小于队列的最大容量maxSize-1,则将数据存入其所指的数组元素中,否则无法存入数据。
只不过这里需要大家注意的一点就是,在将数据存入队列时,你得先判断队列是不是已经满了,而之所以这样做,是因为只有当队列为空或者还没有满的时候,我们才可以往队列里面添数据。
那如何判断队列是否为空,或者是否已满呢?我想,这是大家迫切想要知道的事情,而为了给大家讲清楚这件事情,我还颇费了一些周章,从下面大家也可以看到,我是以图解的方式来给大家进行讲解的,因为这样做大家可以理解的更深刻一点,当然,理解起来也会容易许多。
首先,使用数组来模拟队列,我们得需要两个指针,如下图所示,蓝色箭头表示队列的头指针(即front),红色箭头表示队列的尾指针(即rear)。
代码实现
。。。