目錄
前言
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年清華大學出版社出版的圖書）_百度百科
