数据结构与算法-队列学习笔记

1.概念
队列是一种 $\color{blue}{先进先出}$ 的数据结构。即只能在一端进行插入，在另一端进行删除操作的 $\color{blue}{特殊线性表}$ ,由于队列是一个有序列表，因此它可以用数组或是链表来实现。
$\color{red}{注:}$ 此处的有序指的是插入列表的顺序和输出的顺序相同。

2.数组模拟队列
2.1分析
因为队列的输出、输入分别是从前后端来处理，因此需要两个变量来记录前后端的变化即下标，当插入数据时，rear会随着数据输入而改变；当输出数据时，front则会改变。
由于在使用数组操作数据的输出并不是真正的释放该空间而是变化下标，所以当数组满了就不能使用，导致数组利用率极低不能重复使用，为了解决上述问题，出现了环形队列。

2.2环形队列分析
环形队列中同样需要两个变量来记录数组的两端下标。此时的front表示队列的第一个元素，它的初始值为0；rear指向队列的最后一个元素的最后一个位置，之所以留出一个空位而不是指向最后一个元素是为了方便队满和队空的条件约束，它的初始值为0。
*当队列满时，条件是(rear+1)%maxSize==front
*当队列为空时，font==rear
*队列中存在的有效数据的个数:(rear+maxSize-front)%maxSize

2.3代码实现
class ArrayQueue{
private int front;
private int rear;
private int[] arr;
private int maxSize;
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
}
//判断队列是否为满
public boolean isFull(){
return (rear+1)%maxSize == front
}
//判断队列是否为空
public boolean isEmpty(){
return rear == front;
}
//输入数据
public void addQueue(int value){
if(isFull){
System.out.println("队列已满，不能插入");
}
arr[rear] = value;
rear = (rear + 1)%maxSize;
}
//出队列
public int getValue(){
if(isEmpty){
throw new RuntimeException("队列为空，不能取出数据");
}
int value = arr[front];
// $\color{red}{注：需要考虑取模，否则会导致指针溢出}$
front = (front + 1)%maxSize; //让font后移
return value;
}
$\color{red}{注1：}$ 环形队列中当输入或取出数据的时候会导致rear或者front加1获得新的值，此时我们需要对rear或者front取模否则会导致指针溢出
$\color{red}{注2：}$ 使用环形数组的关键是：清楚rear和front的取值，front指向队列的第一个元素，初始值为0；rear指向队列的最后一个元素的后一个位置