日撸Java三百行（day18：循环队列）

目录

一、顺序队列与循环队列

二、代码实现

1.循环队列创建

2.循环队列遍历

3.循环队列入队

4.循环队列出队

5.数据测试

6.完整的程序代码

总结

---

一、顺序队列与循环队列

在昨天，我们提到队列实现除了采用链式存储结构，还可以采用顺序存储结构（因为队列是线性表，所以和线性表一样也有顺序、链式两种存储结构）。采用顺序存储结构的队列叫做顺序队列，它是用一组地址连续的存储单元依次存放从队头到队尾的队列元素，其中，需要附设头指针head和尾指针tail，分别指向队头元素和队尾元素。

为方便理解，下面我们用图示进行相关说明（假设队列的总存储空间TOTAL_SPACE = 5）：

可以预测，如果我们在元素E之后再插入元素F，那么必然会插入失败，这是因为此时的尾指针tail已经达到队列的最大长度5，所以没办法继续插入元素。但事实上我们可以看到，此时下标为0的存储单元其实是空的，也就是说实际上此时的队列并没有满，这种现象就叫做“假溢出”。

简单来说，“假溢出”的原因就是队列在队头出队、队尾入队，从而造成队头出现空闲单元未被充分利用。为了解决这种“假溢出”现象，避免存储空间浪费，我们将队列的数组看作是头尾相接的循环结构，这种队列头尾相接的循环顺序存储结构就是循环队列，通过这种方式可以重用队头空闲下来的存储单元，如下图：

在循环队列中进行入队、出队操作，头尾指针的指向仍然要+1，不过不同的是，当头尾指针指向TOTAL_SPACE - 1（即头尾指针到达队列的最大长度处）时，此时再+1的结果就变成了头尾指针指向队列下标为0的地方。这种循环意义下的+1操作，可以用以下两种方式进行实现：

• if( i == TOTAL_SPACE - 1) // i表示head或taili = 0;
  elsei++;

• i = (i+1) % TOTAL_SPACE; // i表示head或者tail

对于第二种方式，很明显，当头尾指针指向TOTAL_SPACE - 1（即 i = TOTAL_SPACE - 1）时，i + 1就等于TOTAL_SPACE，进行整除运算后得到余数为0，所以i最后等于0；其余时候，i + 1均小于TOTAL_SPACE，所以整除后得到的余数即为i + 1本身，即i最后就等于i + 1。

通过上图，我们还可以发现，当循环队列为空或者已满时，头指针head均等于尾指针tail，这就会导致一个问题：当head = tail时，到底是判空还是判满？

可以通过以下三种方法来解决这个问题（在今天的代码实现中，我们用的是第二种方法）：

• 另外设置一个布尔变量，用于区别队空和队满。
• 减少一个存储空间的使用，即把TOTAL_SPACE - 1个队列元素视为已满（也就是说，当下标为TOTAL_SPACE - 2的存储空间被占用，尾指针tail指向TOTAL_SPACE - 1时，视为已满），从而将队空和队满区别开来。因此，队空表示为 head = tail，队满表示为（tail + 1）% TOTAL_SPACE = head。

• 设置一个计数器，用于记录当前队列中的元素个数。计数器初始值为0，新元素入队则计数器+1，元素出队则计数器-1，当计数器 = TOTAL_SPACE时，队满；当计数器 = 0时，队空。

二、代码实现

1.循环队列创建

首先，需要创建类，并定义成员变量、成员方法。由于循环队列是基于顺序表，所以这里大体上和顺序表的创建差不多，只需要再增加头指针head、尾指针tail的声明即可，如下：

public class CircleIntQueue {/*** The total space. One space can never be used.*/public static final int TOTAL_SPACE = 10;/*** The data.*/int[] data;/*** The index for calculating the head. The actual head is head % TOTAL_SPACE.*/int head;/*** The index for calculating the tail.*/int tail;/********************* * The constructor******************* */public CircleIntQueue() {data = new int[TOTAL_SPACE];head = 0;tail = 0;} // Of the first constructor

2.循环队列遍历

    /************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";if (head == tail) {return "empty";} // Of iffor (int i = head; i < tail; i++) {resultString += data[i % TOTAL_SPACE] + ", ";} // Of for ireturn resultString;} // Of toString

循环队列的遍历没什么好说的，也是通过重写toString()方法，基本上与之前顺序表的遍历一样。

3.循环队列入队

    /************************ Enqueue.* * @param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {if ((tail + 1) % TOTAL_SPACE == head) {System.out.println("Queue full.");return;} // Of ifdata[tail % TOTAL_SPACE] = paraValue;tail++;} // Of enqueue

由于顺序表的存储空间有上限，所以在入队之前需要先判断是否队满。根据之前的分析，得到队满判断条件为(tail + 1) % TOTAL_SPACE == head；确定队列未满后，进行入队操作，显然此时tail小于TOTAL_SPACE，所以tail % TOTAL_SPACE = tail，data[ tail % TOTAL_SPACE ]就是指已有队列元素后面第一个空的存储单元，将新元素赋给其即可完成入队，最后不要忘了更新尾指针。

4.循环队列出队

    /************************ Dequeue.* * @return The value at the head.**********************/public int dequeue() {if (head == tail) {System.out.println("No element in the queue");return -1;} // Of ifint resultValue = data[head % TOTAL_SPACE];head++;return resultValue;} // Of dequeue

出队只需判断是否队空，而队空的判断条件也十分简单，即head == tail；判断之后，开始出队，因为head小于TOTAL_SPACE，所以head % TOTAL_SPACE = head，data[ head % TOTAL_SPACE ]即为头指针指向的元素，也就是队头的第一个元素；最后，更新头指针，并返回删除的队列元素。

5.数据测试

方法创建完毕后，进行如下的数据测试： 

    /************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {CircleIntQueue tempQueue = new CircleIntQueue();System.out.println("Initialized, the list is: " + tempQueue.toString());for (int i = 0; i < 5; i++) {tempQueue.enqueue(i + 1);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());int tempValue = tempQueue.dequeue();System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());for (int i = 0; i < 6; i++) {tempQueue.enqueue(i + 10);System.out.println("Enqueue, the queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 3; i++) {tempValue = tempQueue.dequeue();System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 6; i++) {tempQueue.enqueue(i + 100);System.out.println("Enqueue, the queue is: " + tempQueue.toString());} // Of for i} // Of main

6.完整的程序代码

package datastructure;/*** Circle int queue.**@auther Xin Lin [e-mail].*/
public class CircleIntQueue {/*** The total space. One space can never be used.*/public static final int TOTAL_SPACE = 10;/*** The data.*/int[] data;/*** The index for calculating the head. The actual head is head % TOTAL_SPACE.*/int head;/*** The index for calculating the tail.*/int tail;/********************* * The constructor******************* */public CircleIntQueue() {data = new int[TOTAL_SPACE];head = 0;tail = 0;} // Of the first constructor/************************ Enqueue.* * @param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {if ((tail + 1) % TOTAL_SPACE == head) {System.out.println("Queue full.");return;} // Of ifdata[tail % TOTAL_SPACE] = paraValue;tail++;} // Of enqueue/************************ Dequeue.* * @return The value at the head.**********************/public int dequeue() {if (head == tail) {System.out.println("No element in the queue");return -1;} // Of ifint resultValue = data[head % TOTAL_SPACE];head++;return resultValue;} // Of dequeue/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";if (head == tail) {return "empty";} // Of iffor (int i = head; i < tail; i++) {resultString += data[i % TOTAL_SPACE] + ", ";} // Of for ireturn resultString;} // Of toString/************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {CircleIntQueue tempQueue = new CircleIntQueue();System.out.println("Initialized, the list is: " + tempQueue.toString());for (int i = 0; i < 5; i++) {tempQueue.enqueue(i + 1);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());int tempValue = tempQueue.dequeue();System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());for (int i = 0; i < 6; i++) {tempQueue.enqueue(i + 10);System.out.println("Enqueue, the queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 3; i++) {tempValue = tempQueue.dequeue();System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 6; i++) {tempQueue.enqueue(i + 100);System.out.println("Enqueue, the queue is: " + tempQueue.toString());} // Of for i} // Of main} // Of class CircleIntQueue

运行结果

总结

循环队列是一种特殊类型的队列，它在传统顺序队列的基础上进行优化，通过“环形结构”充分利用存储空间，避免了空间浪费；虽然相比于链队列，循环队列似乎没有那么方便，不过在固定大小的缓冲区和任务调度等需要高效处理的数据流场景，循环队列还是非常适用的。昨天，我们学习了链队列，今天学习了循环队列，二者都是对于队列实现的模拟，这启示我们对于同一种逻辑结构，有时是可以采用不同的物理存储结构来实现的。