目录
前言
这篇文章介绍循环队列的表示和用法。
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;
}
