1、队列，又称为伫列（Queue），计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
2、队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队（Enqueue），从队列中删除一个队列元素称为出队（Dequeue）。
3、和栈一样，队列是一种操作受限制的线性表。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
4、队列在具体应用中通常用链表或者数组来实现。
用大O符号表示队列的时间复杂度：
| 算法 | 空间 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 平均 | O(n) | O(n) | O(1) | O(1) |
| 最差 | O(n) | O(n) | O(1) | O(1) |
（1）队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize表示该队列的最大容量。
（2）因为队列的输出、输入是分别从前、后端来处理，因此需要两个变量front、rear分别记录队列前、后端的下标。front会随着数据输出而改变，rear则是随着数据输入而改变，如图所示：
front是队列最前一个元素[不含]
rear是队列最后一个元素[含]
（3）当我们将数据存入队列时称为”addQueue”操作，它需要两个步骤实现：
① 将尾指针往后移，即rear + 1。当front = rear时，则队列为空。
② 若尾指针rear小于队列的最大下标减1，即rear < maxSize - 1（此处的maxSize - 1就是数组最大索引），则将数据存入rear所指的数组元素中，否则无法存入数据，即当rear = maxSize - 1时，队列已满。
数组模拟队列：
package com.example.datastructure.queue;
/**
* @author Administrator
* @date 2020/12/30
* <p>
* 用数组模拟队列
*/
class ArrayQueue {
/**
* 表示数组的最大容量
*/
private int maxSize;
/**
* 队列头
*/
private int front;
/**
* 队列尾
*/
private int rear;
/**
* 用于存放数据，模拟度列
*/
private int[] array;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
array = new int[maxSize];
// 指向队列头的前一个位置
front = -1;
// 指向队列尾部的最后一个数据
rear = -1;
}
/**
* 判断队列是否已满
*/
public boolean isFull() {
return rear == maxSize - 1;
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
return rear == front;
}
/**
* 添加数据到队列
*/
public void addQueue(int data) {
if (isFull()) {
System.out.println("队列满，不能添加数据");
return;
}
// 让rear后移
rear++;
array[rear] = data;
}
/**
* 获取队列的数据，出队列
*/
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空，不能取数据");
}
// front后移
front++;
return array[front];
}
/**
* 显示队列的所有数据
*/
public void showQueue() {
if (isEmpty()) {
System.out.println("队列空的，没有数据");
return;
}
for (int i = 0; i < array.length; i++) {
System.out.printf("array[%d]=%d\n", i, array[i]);
}
}
/**
* 显示队列头的数据，但并不取出
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据");
}
return array[front + 1];
}
}
对数组模拟队列进行测试，测试代码如下：
package com.example.datastructure.queue;
import java.util.Scanner;
/**
* @author Administrator
* @date 2021/1/12
* 测试-数组模拟队列
*/
class ArrayQueueDemo {
public static void main(String[] args) {
// 测试
ArrayQueue queue = new ArrayQueue(3);
// 接收用户的输入
char key;
Scanner scanner = new Scanner(System.in);
boolean loop = true;
// 输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
System.out.println("e(exit):退出程序");
// 接收一个字符
key = scanner.next().charAt(0);
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("添加一个数据");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g':
try {
int data = queue.getQueue();
System.out.printf("取出的数据是%d\n", data);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int headValue = queue.headQueue();
System.out.printf("队列头的数据是%d\n", headValue);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
测试效果：
问题：数组使用一次就不能用了，没有达到复用的效果（数组只能使用一次，数据出队列后无法继续使用，不能重新添加数据）。
优化：使用算法（取模：%），将其改造为环形队列。
对前面的数组模拟队列进行优化，将数组看做是一个环(通过取模%的方式实现)，就可以解决数组无法复用的问题，从而充分利用数组。
（1）front变量的含义做一个调整：front的初始值为0，front就指向队列的第一个元素，即arr[front]就是队列的第一个元素。
（2）rear变量的含义做一个调整：rear的初始值为0，rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定。即，尾索引的下一个为头索引时表示队列已满。
（3）当(rear + 1) % maxSize = front时，队列已满。
（4）对rear = front时，队列为空。
（5）经上述分析，队列中有效的数据个数 = (rear + maxSize - front) % maxSize。
经以上调整，我们就可以修改原来的数组模拟队列，得到一个新的环形队列。
经典公式：
对于一个固定大小的数组，任何位置都可以是队首，只要知道队列长度，就可以根据下面公式计算出队尾位置：
tailIndex = (headIndex + count − 1) mod capacity
其中capacity是数组长度，count是队列长度，headIndex和tailIndex分别是队首head和队尾tail索引。
数组模拟环形队列：
package com.example.datastructure.queue;
/**
* @author Administrator
* @date 2020/12/30
* <p>
* 用数组模拟环形队列
*/
class CircleArrayQueue {
/**
* 表示数组的最大容量
*/
private int maxSize;
/**
* front变量的含义做一个调整：
* front的初始值为0，front就指向队列的第一个元素，即arr[front]就是队列的第一个元素。
*/
private int front;
/**
* rear变量的含义做一个调整：
* rear的初始值为0，rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定。
* 即，尾索引的下一个为头索引时表示队列已满。
*/
private int rear;
/**
* 用于存放数据，模拟队列
*/
private int[] array;
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
array = new int[maxSize];
}
/**
* 判断队列是否已满
*/
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
return rear == front;
}
/**
* 添加数据到队列
*/
public void addQueue(int data) {
if (isFull()) {
System.out.println("队列满，不能加入更多~");
return;
}
array[rear] = data;
// 将rear后移，这里必须考虑取模
rear = (rear + 1) % maxSize;
}
/**
* 获取队列数据，出队列
*/
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空，无数据出列~");
}
/*
这里需要分析出front是指向队列的第一个元素.
1、先把front对应的值保留到一个临时变量
2、将front后移，考虑取模
3、将临时变量返回
*/
int temp = array[front];
front = (front + 1) % maxSize;
return temp;
}
/**
* 显示队列全部数据
*/
public void showQueue() {
if (isEmpty()) {
System.out.println("队列空，没有显示内容~");
return;
}
/*
思路：从front开始遍历
*/
for (int i = front; i < front + effectiveNum(); i++) {
System.out.printf("array[%d]=%d\n", i % maxSize, array[i % maxSize]);
}
}
/**
* 求出当前队列有效数据个数
*/
public int effectiveNum() {
return (rear + maxSize - front) % maxSize;
}
/**
* 显示队列头数据，但不出列
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空，无头数据~");
}
return array[front];
}
/**
* 获取队尾数据，不出列
*/
public int rearQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空，无尾数据~");
}
return array[(rear - 1) & (array.length - 1)];
}
}
测试环形队列：
package com.example.datastructure.queue;
import java.util.Scanner;
/**
* @author Administrator
* @date 2021/1/20
*/
class CircleArrayQueueDemo {
public static void main(String[] args) {
System.out.println("测试数组模拟环形队列：");
//说明：设置为4，则队列的有效数据个数为3
CircleArrayQueue circleQueue = new CircleArrayQueue(4);
char key;
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show): 显示队列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列取出数据");
System.out.println("h(head): 查看队列头的数据");
System.out.println("r(rear): 查看队尾的数据");
// 接收一个字符
key = scanner.next().charAt(0);
switch (key) {
case 's':
circleQueue.showQueue();
break;
case 'a':
System.out.println("添加数据：");
int value = scanner.nextInt();
circleQueue.addQueue(value);
break;
case 'g':
try {
int res = circleQueue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = circleQueue.headQueue();
System.out.printf("队列的头数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'r':
try {
int r = circleQueue.rearQueue();
System.out.printf("队尾的数据是%d\n", r);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
测试效果：
说明：
本文整理自韩顺平老师的课程，强烈推荐韩老师的课。
微信公众号: TechU
