数据结构与算法学习笔记九---循环队列的表示和实现(C++)
目录
前言
1.为什么要使用循环队列
2.队列的顺序存储方式的实现
1.定义
2.队列初始化
3.销毁
4.清空队列
5.队列是否为空
6.队列长度
7.队头
8.入队
9.出队
10.遍历队列
11.完整代码
3.参考资料
前言
这篇文章介绍循环队列的表示和用法。
1.为什么要使用循环队列
在上一篇文章中，我们知道了顺序的循环表示和实现方法。但是我们会发现当我们在操作顺序链表的时候，我们频繁的操作顺序队列，而队列又不为空的时候，出队列的一些存储空间会变得不可用。
如下图所示，当我rear=3,front=2的时候，顺序队列中至少有连个存储空间空间是不可以使用的，这无疑会浪费一些存储空间。那么有没有办法让我们在出队列之后，重复利用之前存储空间呢，答案是有的。
图1.顺序队列的出队列和入队列操作示意图
这里借鉴了网上老师的三种解决方案：
1.使用计数器记录队列中的元素个数
2.加标志位，删除的时候标志位置1，插入置0，当front = rear并且标志位为0，表示队列为空，当front=rear并且标志位为1的时候，表示队列经满。
3.认为浪费一个存储空间，改成一个循环队列来实现。
这里下面代码的表示和实现采用的第三种方案。
关于循环队列的理解，感觉严蔚敏老师的讲解还是不错的，直接贴个图吧。
图2.严蔚敏老师数据结构与算法中关于循环队列的思路
2.队列的顺序存储方式的实现
1.定义
struct CircularQueue {int *base;int front;int rear;int maxSize; // 队列的最大容量
};2.队列初始化
// 队列初始化
Status initQueue(CircularQueue &circularQueue, int maxSize) {circularQueue.base = new int[maxSize]; // 为循环队列分配内存if (!circularQueue.base) {return 0; // 内存分配失败}circularQueue.front = circularQueue.rear = 0; // 初始化队首和队尾指针circularQueue.maxSize = maxSize;return 1; // 初始化成功
}
3.销毁
// 销毁队列
void destroyQueue(CircularQueue &circularQueue) {if (circularQueue.base) {delete[] circularQueue.base; // 释放内存circularQueue.base = nullptr; // 将指针置为空}
}4.清空队列
// 清空队列
void clearQueue(CircularQueue &circularQueue) {circularQueue.front = circularQueue.rear = 0; // 重置队首和队尾指针
}5.队列是否为空
// 判断队列是否为空
bool isEmptyQueue(CircularQueue &circularQueue) {return circularQueue.front == circularQueue.rear; // 当队首和队尾指针相同时，队列为空
}6.队列长度
// 获取队列长度
int queueLength(CircularQueue &circularQueue) {return (circularQueue.rear - circularQueue.front + circularQueue.maxSize) % circularQueue.maxSize;
}7.队头
// 获取队首元素
Status getQueueFront(CircularQueue &circularQueue, int &frontElement) {if (isEmptyQueue(circularQueue)) {return 0; // 队列为空}frontElement = circularQueue.base[circularQueue.front];return 1; // 成功获取队首元素
}8.入队
// 入队
bool enQueue(CircularQueue &circularQueue, int element) {// 检查队列是否已满if ((circularQueue.rear + 1) % circularQueue.maxSize == circularQueue.front) {return false; // 队列已满}// 入队操作circularQueue.base[circularQueue.rear] = element;circularQueue.rear = (circularQueue.rear + 1) % circularQueue.maxSize; // 移动队尾指针return true; // 入队成功
}9.出队
// 出队
bool deQueue(CircularQueue &circularQueue, int &element) {// 检查队列是否为空if (isEmptyQueue(circularQueue)) {return false; // 队列为空，无法出队}// 出队操作element = circularQueue.base[circularQueue.front];circularQueue.front = (circularQueue.front + 1) % circularQueue.maxSize; // 移动队首指针return true; // 出队成功
}10.遍历队列
// 遍历队列
void traverseQueue(CircularQueue &circularQueue) {// 遍历队列并打印元素int i = circularQueue.front;while (i != circularQueue.rear) {cout << circularQueue.base[i] << " ";i = (i + 1) % circularQueue.maxSize;}cout << endl;
}11.完整代码
#include <iostream>
using namespace std;typedef int Status;struct CircularQueue {int *base;int front;int rear;int maxSize; // 队列的最大容量
};// 队列初始化
Status initQueue(CircularQueue &circularQueue, int maxSize) {circularQueue.base = new int[maxSize]; // 为循环队列分配内存if (!circularQueue.base) {return 0; // 内存分配失败}circularQueue.front = circularQueue.rear = 0; // 初始化队首和队尾指针circularQueue.maxSize = maxSize;return 1; // 初始化成功
}// 销毁队列
void destroyQueue(CircularQueue &circularQueue) {if (circularQueue.base) {delete[] circularQueue.base; // 释放内存circularQueue.base = nullptr; // 将指针置为空}
}// 清空队列
void clearQueue(CircularQueue &circularQueue) {circularQueue.front = circularQueue.rear = 0; // 重置队首和队尾指针
}// 判断队列是否为空
bool isEmptyQueue(CircularQueue &circularQueue) {return circularQueue.front == circularQueue.rear; // 当队首和队尾指针相同时，队列为空
}// 获取队列长度
int queueLength(CircularQueue &circularQueue) {return (circularQueue.rear - circularQueue.front + circularQueue.maxSize) % circularQueue.maxSize;
}// 获取队首元素
Status getQueueFront(CircularQueue &circularQueue, int &frontElement) {if (isEmptyQueue(circularQueue)) {return 0; // 队列为空}frontElement = circularQueue.base[circularQueue.front];return 1; // 成功获取队首元素
}// 入队
bool enQueue(CircularQueue &circularQueue, int element) {// 检查队列是否已满if ((circularQueue.rear + 1) % circularQueue.maxSize == circularQueue.front) {return false; // 队列已满}// 入队操作circularQueue.base[circularQueue.rear] = element;circularQueue.rear = (circularQueue.rear + 1) % circularQueue.maxSize; // 移动队尾指针return true; // 入队成功
}// 出队
bool deQueue(CircularQueue &circularQueue, int &element) {// 检查队列是否为空if (isEmptyQueue(circularQueue)) {return false; // 队列为空，无法出队}// 出队操作element = circularQueue.base[circularQueue.front];circularQueue.front = (circularQueue.front + 1) % circularQueue.maxSize; // 移动队首指针return true; // 出队成功
}// 遍历队列
void traverseQueue(CircularQueue &circularQueue) {// 遍历队列并打印元素int i = circularQueue.front;while (i != circularQueue.rear) {cout << circularQueue.base[i] << " ";i = (i + 1) % circularQueue.maxSize;}cout << endl;
}int main() {CircularQueue circularQueue;int maxSize = 10; // 队列的最大容量initQueue(circularQueue, maxSize); // 初始化循环队列// 测试入队for (int i = 1; i <= 5; ++i) {enQueue(circularQueue, i * 10);}// 输出队列元素cout << "队列元素：";traverseQueue(circularQueue);// 获取队首元素int frontElement;if (getQueueFront(circularQueue, frontElement)) {cout << "队首元素：" << frontElement << endl;}// 测试出队int element;for (int i = 0; i < 3; ++i) {if (deQueue(circularQueue, element)) {cout << "出队元素：" << element << endl;}}// 输出队列元素cout << "队列元素：";traverseQueue(circularQueue);// 判断队列是否为空if (isEmptyQueue(circularQueue)) {cout << "队列为空" << endl;} else {cout << "队列不为空" << endl;}// 获取队列长度cout << "队列长度：" << queueLength(circularQueue) << endl;// 清空队列clearQueue(circularQueue);// 判断清空后队列是否为空if (isEmptyQueue(circularQueue)) {cout << "清空队列后，队列为空" << endl;} else {cout << "清空队列后，队列不为空" << endl;}// 销毁队列destroyQueue(circularQueue);return 0;
}
3.参考资料
1.B站上看到的一个老师的讲解
2.数据结构C语言版（1997年清华大学出版社出版的图书）_百度百科