1. 概述
1.1 定义
一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
1.2 队列的基本操作
- 入队
- 出队
- 队列元素个数
- 判断队列是否为空
- 获取队首元素
2. 分类
2.1 顺序队列（数组实现）
2.1.1 溢出现象-真溢出/下溢
溢出现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
真溢出现象：当队列满时，做进栈运算产生空间溢出的现象。真溢出是一种出错状态，应设法避免。
假溢出现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
2.1.2 Java代码实现
package com.example.data_structure;
/**
* 描述:
* 数组队列实现
*
* @author XueGuCheng
* @create 2022-09-24 15:50
*/
public 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];
// 指向队首的前一个位置
this.front = -1;
// 指向队列尾部，包括队列最后的这个数据
this.rear = -1;
}
// 判断队列是否满了
public boolean isFull(){
return rear == maxSize -1;
}
// 判断队列是否为空
public boolean isEmpty(){
return front == rear;
}
// 入队
public void push(int data){
if (isFull()){
// 扩容
return;
}
// 更新队尾指针
rear++;
// 从队尾插入新元素
array[rear] = data;
}
// 出队
public int pop(){
if (isEmpty()){
throw new RuntimeException("队列为空!");
}
// 更新头指针
front++;
// 移除队列头元素
return array[front];
}
// 查看队列头元素
public int head(){
if (isEmpty()){
throw new RuntimeException("队列为空!");
}
return array[front + 1];
}
public void print(){
for (int i = 0;i <= array.length - 1; i++){
System.out.println(array[i]);
}
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(5);
queue.push(0);
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
queue.print();
}
}
2.2 环形队列（数组实现）
2.2.1 定义
环形队列是一种特殊的队列结构，保证了元素也是先进先出的，但与一般队列的区别是，他们是环形的，即队列头部的上个元素是队列尾部，通常是容纳元素数固定的一个闭环。
2.2.2 概述
1.判断为空
由上图可以看出，环形队列判断为空的条件即rear == front
2.元素入队
元素的入队，假定插入元素 rear= rear+1，删除元素 front = front +1；如下图所示，ABC入队的后，此时rear = 3；
当元素插满后，此时 rear = 0，front = 1；
所以，插入元素 rear= rear+1，不满足此情况（5 + 1 ≠ 0），而是rear = （rear+1）% maxSize;
3.元素出队
从元素入队的推断公式，同样可以得出 front= （front+1）% maxSize;
4.判断为满
当在第一圈时，队列加满元素时：rear =5， front = 0； （rear +1 == front） 此时rear + 1=6 ，front =0 显然不相等，同样和出入队列一样对长度进行取模，（（rear +1）% maxSize == front）。
2.2.3 代码实现
package com.example.data_structure;
/**
* 描述:
* 数组队列实现
*
* @author XueGuCheng
* @create 2022-09-24 15:50
*/
public class CircleArrayQueue {
/**
* 表示数组的最大容量
*/
private int maxSize;
/**
* 队列头
*/
private int front;
/**
* 队列尾
*/
private int rear;
/**
* 存放队列元素
*/
private int[] array;
// 初始化
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
array = new int[maxSize];
this.front = 0;
this.rear = 0;
}
// 判断队列是否满了
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
// 判断队列是否为空
public boolean isEmpty(){
return front == rear;
}
// 入队
public void push(int data){
if (isFull()){
// 扩容
return;
}
// 从队尾插入新元素
array[rear] = data;
// 更新队尾指针
rear = (rear + 1) % maxSize;
}
// 出队
public int pop(){
if (isEmpty()){
throw new RuntimeException("队列为空!");
}
// 移除队列头元素
int temp = array[front];
// 更新头指针
front = (front + 1) % maxSize;
return temp;
}
// 查看队列头元素
public int head(){
if (isEmpty()){
throw new RuntimeException("队列为空!");
}
return array[front];
}
public void print(){
if (isEmpty()){
throw new RuntimeException("队列为空!");
}
for (int i = 0;i < front + size(); i++){
System.out.println(array[i % maxSize]);
}
}
// 队列长度
public int size(){
return (rear + maxSize - front) % maxSize;
}
}