数据结构与算法学习笔记九---循环队列的表示和实现(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年清华大学出版社出版的图书）_百度百科