下载掌阅APP，畅读海量书库
立即打开
队列是在一端进行插入操作，另一端进行删除操作的线性表。队列只允许先进先出（First In First Out，FIFO）。
队列的数据元素称为队列元素。在队列中插入一个元素称为入队，进行入队操作的一端称为队尾。从队列中删除一个元素称为出队，进行出队操作的一端称为队头。队列结构如图2-25所示。
图2-25 队列结构示意图
将队列的相关操作定义成Queue接口，代码如下：
顺序队列是基于顺序结构实现的队列。顺序队列出队的实现分为两种：
（1）队列头部不移动，队列头部后的所有元素向前移动，如图2-26所示。
以这种方式实现的出队缺点是每次队列头部的元素出队后，需要依次移动队列头部后的所有元素，出队效率不高。
图2-26 队列头部后的所有元素向前移动示意图
（2）队列头部移动，出队后队列头部向后移动一个位置，如图2-27所示。
这种方式实现的出队会造成“假溢出现象”，即顺序队列因多次入队列和出队列操作后出现尚有存储空间但不能进行入队列操作的溢出，如图2-28所示。相比于第（1）种队列头部不移动的方式，队列头部移动的方式实现的出队编码稍微复杂一些。
图2-27 出队后队头移动示意图
图2-28 假溢出示意图
本节以第（1）种方式实现顺序队列，代码实现如下：
创建顺序队列测试类，验证顺序队列的功能。测试代码如下：
执行顺序队列测试类，测试结果如下：
----------队列是否为空----------
false
----------队列是否已满----------
true
----------队列元素个数----------
10
----------打印队列元素----------
0 1 2 3 4 5 6 7 8 9
为了有效解决假溢出的问题，当顺序结构存储的队列中的元素到达最大容量后，从头开始重新利用未使用的存储空间，即形成头尾相连的循环。这种首尾相连的存储结构实现的队列称为循环队列。循环队列如图2-29所示。
图2-29 循环队列示意图
循环队列在队列为空和队列已满时，队头和队尾都会相遇，如图2-30所示。此时仅用队头和队尾相遇这个条件将不能有效区分队列是否为空或者队列是否已满。
图2-30 队头和队尾相遇情况示意图
为了解决以上问题，可以使用如下改进方案。假设队尾位置是tail，队头位置为head，队列最大容量为capacity。
【方案1】 设置一个标志位flag，初始时flag=0，每当入队成功设置flag=1，每当出队成功设置flag=0。在【方案1】的前提下，重新分析队列为空和队列已满的情况。
（1）队列为空的条件为：head=tail并且flag=0。
（2）队列已满的条件为：head=tail并且flag=1。
【方案2】 预留一个存储空间不使用。在【方案2】的前提下，重新分析队列为空和队列已满的情况。
（1）队列为空的条件为：(head+1) % capacity = tail。
（2）队列已满的条件为：(tail+1) % capacity = head。
【方案3】 设计一个计数器count，统计队列中的元素个数。在【方案3】的前提下，重新分析队列为空和队列已满的情况。
（1）队列为空的条件为：count=0。
（2）队列已满的条件为：count=capacity。
本节将采用【方案3】的方法实现循环链表。循环链表代码如下：
创建循环队列测试类，验证循环队列的功能。测试代码如下：
执行循环队列测试类，测试结果如下：
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
----------队列是否为空----------
false
----------队列是否已满----------
true
----------队列元素个数----------
10
----------打印队列元素----------
0 1 2 3 4 5 6 7 8 9
从测试结果可以看出，当调用入栈方法尝试将20个元素加入循环队列中，循环队列已满后将无法加入元素。整个队列中只存储了0～9这10个元素。
链式队列是使用链式存储方式实现的队列。链式队列如图2-31所示。
图2-31 链式队列示意图
链式队列实现如下：
创建链式队列测试类，验证链式队列的功能。测试代码如下：
执行链式队列测试类，测试结果如下：
----------队列是否为空----------
false
----------队列元素个数----------
10
----------打印队列元素----------
0 1 2 3 4 5 6 7 8 9
----------队列元素个数----------
0
在优先队列中，元素被赋予优先级。优先队列入队与其他队列没有差别。当出队时，具有最高优先级的元素最先出队。优先队列具有最高级先出（First In Largest Out）的特点。
优先队列分为两种：
（1）最大优先队列：无论入队顺序，当前最大的元素优先出队。
（2）最小优先队列：无论入队顺序，当前最小的元素优先出队。
本节使用顺序存储结构实现最大优先队列。
创建顺序存储结构实现最大优先队列测试类，验证顺序存储结构实现的最大优先队列的功能。测试代码如下：
执行最大优先队列测试类，测试结果如下：
编号是2的元素出队，该元素优先级90
编号是5的元素出队，该元素优先级80
编号是4的元素出队，该元素优先级50
编号是3的元素出队，该元素优先级40
编号是1的元素出队，该元素优先级30
从顺序存储结构实现最大优先队列的代码可知，顺序存储结构实现最大优先队列每次出队都要比较每个元素的优先级，即时间复杂度为O(n)。
顺序存储结构并非是实现优先队列的唯一方式，感兴趣的读者可以自行使用链式存储结构实现。与线性存储结构相比，堆数据结构是更加常见的实现优先队列的方式，详情可参考4.5节。
（1）队列的概念：队列是在一端进行插入操作，另一端进行删除操作的线性表。
（2）队列的特点：先进先出。
（3）队列的存储：
· 顺序队列。
· 链式队列。
（4）JDK中的实现：JDK中的LinkedList实现了队列，PriorityQueue实现了优先队列。