1.2 队列-循环链表
本文最后更新于 2024-07-06，文章内容可能已经过时。
1.2 队列-循环队列
一.顺序 队列
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变。
数组模拟顺序队列
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：
- 将尾指针往后移：rear+1 , 当front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
/**
* desc: 使用数组模拟队列
* @author GreyPigeon mail:2371849349@qq.com
* @since 2024-01-08-14:53
**/
public 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("e(exit): 退出程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列取出数据");
System.out.println("h(head): 查看队列头的数据");
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 res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
//编写一个ArrayQueue类
class ArrayQueue{
private int maxSize; //表示数组的最大容量
private int front; //队列头
private int rear; //队列尾
private int[] arr; //该数据用于存放数据，模拟队列
//创建队列的构造器（初始化）
public ArrayQueue(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; //指向队列头部，分析出front是指向front是指向队列头的前一个位置。
rear = -1; //指向队列尾部，指向队列尾的的数据（即最后一个数据）。
}
//判断队列是否已满
public boolean isFull(){
return rear == maxSize - 1;
}
//判断队列是否为空
public boolean isEmpty(){
return rear == front;
}
//添加数据到队列
public void addQueue(int n){
//判断队列是否已满
if (isFull()) {
System.out.println("队列已满，不能添加数据~");
return;
}
rear++; //让rear后移
arr[rear] = n;
}
//获取队列的数据，出队列
public int getQueue(){
//判断队列是否为空
if (isEmpty()) {
//抛出异常
throw new RuntimeException("队列为空，不能获取数据");
}
front++; //front后移（因为front始终指向第一个数据的前一个位置）
return arr[front];
}
//显示队列的所有数据
public void showQueue(){
//遍历
if (isEmpty()) {
System.out.println("队列为空，没有数据");
return;
}
for(int i = 0; i < arr.length; i++){
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
//显示队列的头数据，注意不是取出数据
public int headQueue(){
//判断是否为空
if(isEmpty()){
throw new RuntimeException("队列为空，没有数据");
}
return arr[front +1];
}
}
三. 顺序队列假溢出
什么是假溢出？这里需要考虑到顺序队列有什么缺点，对于顺序队列而言，其存在已经足够解决大多时候的设计问题了，但是其依旧存在一些缺陷和不足。由于入队和出队操作均是直接在其后面进行结点的链接和删除，这种操作会造成其使用空间不断向出队的那一边偏移，产生假溢出。
假设一个队列的总个数不超过5个，经过5次入队操作和两次出队操作后，如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。
四. 循环队列
解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。
但由于空队列时，fromt等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？
- 办法一是设置一个标志变量fiag，当front= rear，且fag=0时为队列空，当font=rear，且filag = 1时为队列满。
- 办法二是当队列空时，条件就是front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。
我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) % QueueSize ==front （取模“%”的目的就是为了整合rear与front大小为一个问题）。
通用的就计算队列长度的公式：(rear - front + QueueSize) % QueueSize
五. 数组模拟循环队列
- front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front)就是队列的第一个元素
front的初始值=0。 - rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定
rear的初始值=0。
/**
* desc:使用数组模拟循环队列
* @author GreyPigeon mail:2371849349@qq.com
* @since 2024-01-08-17:55
**/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
System.out.println("测试数组模拟环形队列的案例~~~");
// 创建一个环形队列
CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3
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): 查看队列头的数据");
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 res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // 查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
class CircleArray {
private int maxSize; // 表示数组的最大容量
//front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
//front 的初始值 = 0
private int front;
//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
//rear 的初始值 = 0
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// 判断队列是否满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
// 添加数据到队列
public void addQueue(int n) {
// 判断队列是否满
if (isFull()) {
System.out.println("队列满，不能加入数据~");
return;
}
//直接将数据加入
arr[rear] = n;
//将 rear 后移, 这里必须考虑取模
rear = (rear + 1) % maxSize;
}
// 获取队列的数据, 出队列
public int getQueue() {
// 判断队列是否空
if (isEmpty()) {
// 通过抛出异常
throw new RuntimeException("队列空，不能取数据");
}
// 这里需要分析出 front是指向队列的第一个元素
// 1. 先把 front 对应的值保留到一个临时变量
int value = arr[front];
// 2. 将 front 后移, 考虑取模,防止越界
front = (front + 1) % maxSize;
// 3. 将临时保存的变量返回
return value;
}
// 显示队列的所有数据
public void showQueue() {
// 遍历
if (isEmpty()) {
System.out.println("队列空的，没有数据~~");
return;
}
// 思路：从front开始遍历，遍历多少个元素？size()
// arr的下标不一定是i，需要取模 （即使下标在长度范围内）
for (int i = front; i < front + size() ; i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// 求出当前队列有效数据的个数
public int size() {
// rear = 2
// front = 1
// maxSize = 3
return (rear + maxSize - front) % maxSize;
}
// 显示队列的头数据， 注意不是取出数据
public int headQueue() {
// 判断是否为空
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据~~");
}
return arr[front]; //front为队列的第一个元素
}
}
参考：《大话数据结构》、尚硅谷
- 感谢你赐予我前进的力量
-
微信 
支付宝
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 程序员Graypigeon
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
