@[toc]
一、使用场景
- 银行排队，先到先得
- 测核酸，先到先测
二、队列介绍
1) 队列是一个有序列表, 可以用数组或是链表来实现。
2) 遵循先入先出的原则。即: 先存入队列的数据, 要先取出。后存入的要后取出
3) 示意图: (使用数组模拟队列示意图)
三、数组模拟队列
3.1 思路分析
- 队列本身是有序列表, 若使用数组的结构来存储队列的数据, 则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
- 因为队列的输出、输入是分别从前后端来处理, 因此需要两个变量 front 及 rear 分别记录队列前后端的下标, front 会随着数据输出而改变, 而 rear则是随着数据输入而改变, 如图所示:
当我们将数据存入队列时称为” addQueue”, addQueue 的处理需要有两个步骤: 思路分析
1）将尾指针往后移: rear $+1$, 当 front $==$ rear 【空】
2）若尾指针 rear 小于队列的最大下标 maxSize-1, 则将数据存入 rear 所指的数组元素中, 否则无法存入数据。 rear $==\max$ Size $-1$ [队列满]
3.2 Java代码实现
public class ArrayQueue {
public static void main(String[] args) {
// 1. 声明数组模拟的队列，设置maxSize为4
ArrayQueue arrayQueue = new ArrayQueue(4);
// 2. 开始测试
arrayQueue.add(1);
arrayQueue.add(3);
arrayQueue.add(4);
arrayQueue.add(2);
arrayQueue.add(5);
System.out.println(arrayQueue.poll());
System.out.println(arrayQueue.poll());
System.out.println(arrayQueue.poll());
System.out.println(arrayQueue.poll());
System.out.println(arrayQueue.poll());
}
// 数组长度（队列的最大容量）
int maxSize;
// 当前队列长度
int curSize;
// 数组
int[] arr;
// 当前指向的元素
int curIndex;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
curIndex = 0;
curSize = 0;
}
// 添加元素到队列
public void add(int num) {
if (curSize >= maxSize) {
System.err.println("队列容量不足，无法添加元素");
}else{
arr[curSize++] = num;
}
}
// 从队列取出头元素
public int poll() {
if (curIndex >= curSize) {
throw new RuntimeException("当前队列为空，无法取出元素");
}else if (curIndex >= maxSize) {
throw new RuntimeException("超出队列长度");
}else{
return arr[curIndex++];
}
}
}输出：
队列容量不足，无法添加元素
1
3
4
2
Exception in thread "main" java.lang.RuntimeException: 当前队列为空，无法取出元素
at com.wskh.DataStructures.Queue.ArrayQueue.poll(ArrayQueue.java:57)
at com.wskh.DataStructures.Queue.ArrayQueue.main(ArrayQueue.java:26)3.3 问题分析与优化
1) 目前数组使用一次就不能用, 没有达到复用的效果
2) 将这个数组使用算法, 改进成一个环形的队列 取模：%
四、数组模拟环形队列
4.1 思路分析
对前面的数组模拟队列的优化, 充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明:
1) 尾索引的下一个为头索引时表示队列满, 即将队列容量空出一个作为约定, 这个在做判断队列满的 时候需要注意 $($ rear $+1) \%$ maxSize $=$ front 满]
2) rear $==$ front $[$ 空 $]$
3) 分析示意图:
4.2 Java代码实现
public class CircleArrayQueue {
public static void main(String[] args) {
// 1. 声明数组模拟的队列，设置maxSize为4
CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
// 2. 开始测试
circleArrayQueue.add(1);
circleArrayQueue.add(3);
circleArrayQueue.add(4);
System.out.println(circleArrayQueue.poll());
System.out.println(circleArrayQueue.poll());
circleArrayQueue.add(2);
circleArrayQueue.add(5);
System.out.println(circleArrayQueue.poll());
System.out.println(circleArrayQueue.poll());
System.out.println(circleArrayQueue.poll());
}
// 数组长度（队列的最大容量）
int maxSize;
// 当前队列长度
int curSize;
// 当前追加的指针
int addIndex;
// 数组
Integer[] arr;
// 当前指向的元素
int curIndex;
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new Integer[maxSize];
curIndex = 0;
curSize = 0;
addIndex = 0;
}
// 添加元素到队列
public void add(int num) {
if (curSize >= maxSize) {
System.err.println("队列容量不足，无法添加元素");
} else {
arr[(addIndex++) % maxSize] = num;
}
}
// 从队列取出头元素
public int poll() {
if (arr[curIndex % maxSize] == null) {
throw new RuntimeException("当前队列为空，无法取出元素");
} else {
curSize--;
Integer integer = arr[curIndex % maxSize];
arr[curIndex % maxSize] = null;
curIndex++;
return integer;
}
}
}输出：
1
3
4
2
5