【10.2】隊列-設計循環隊列

一、題目

????????設計你的循環隊列實現。循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”。

????????循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。

你的實現應該支持如下操作：

MyCircularQueue(k): 構造器，設置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環隊列是否為空。
isFull(): 檢查循環隊列是否已滿。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 設置長度為 3
circularQueue.enQueue(1); ?// 返回 true
circularQueue.enQueue(2); ?// 返回 true
circularQueue.enQueue(3); ?// 返回 true
circularQueue.enQueue(4); ?// 返回 false，隊列已滿
circularQueue.Rear(); ?// 返回 3
circularQueue.isFull(); ?// 返回 true
circularQueue.deQueue(); ?// 返回 true
circularQueue.enQueue(4); ?// 返回 true
circularQueue.Rear(); ?// 返回 4

提示：

所有的值都在 0?至 1000 的范圍內；
操作數將在 1 至 1000 的范圍內；
請不要使用內置的隊列庫。

二、解題思路

2.1 數組實現

????????我們可以通過數組來模擬循環隊列，利用數組的索引構建一個虛擬的環形結構。在循環隊列中，設置兩個指針：隊尾 `rear` 和隊首 `front`，隊列的大小是固定的。結構如下圖所示：

????????在循環隊列中，當隊列為空時，`front` 和 `rear` 相等，即 `front == rear`；而當隊列的所有空間都被占滿時，同樣會出現 `front == rear` 的情況。為了區分這兩種狀態，我們規定隊列的數組容量為 `capacity`，但循環隊列最多只能存儲 `capacity - 1` 個元素。當隊列中只剩下一個空閑的存儲單元時，就認為隊列已滿。因此，隊列判空的條件是 `front == rear`，而判滿的條件是 `front == (rear + 1) % capacity`。

????????對于一個固定大小的數組，只要知道隊尾 `rear` 和隊首 `front`，就可以計算出隊列的當前長度：? (rear - front + capacity) mod capacity

循環隊列的主要屬性如下：

????????**`elements`**：一個固定大小的數組，用于存儲循環隊列的元素。
????????**`capacity`**：循環隊列的容量，即隊列中最多可以容納的元素數量。
????????**`front`**：隊首元素在數組中的索引。
????????**`rear`**：隊尾元素的下一個位置的索引。

循環隊列的接口方法如下：

????????**`MyCircularQueue(int k)`**：初始化隊列，數組的空間大小為 `k + 1`，并將 `front` 和 `rear` 初始化為 0。
????????**`enQueue(int value)`**：在隊列的尾部插入一個元素，并將 `rear` 更新為 `(rear + 1) % capacity`。
????????**`deQueue()`**：從隊首取出一個元素，并將 `front` 更新為 `(front + 1) % capacity`。
????????**`Front()`**：返回隊首的元素，需要先檢測隊列是否為空。
????????**`Rear()`**：返回隊尾的元素，需要先檢測隊列是否為空。
????????**`isEmpty()`**：檢測隊列是否為空，只需判斷 `rear` 是否等于 `front`。
????????**`isFull()`**：檢測隊列是否已滿，只需判斷 `front` 是否等于 `(rear + 1) % capacity`。

????????通過這種方式，循環隊列能夠高效地利用數組空間，同時避免普通隊列在空間利用上的不足。

#include <iostream>
#include <vector>
using namespace std;class MyCircularQueue {
private:int front;           // 隊首指針int rear;            // 隊尾指針int capacity;        // 隊列容量vector<int> elements; // 用于存儲隊列元素的數組public:// 構造函數，初始化隊列MyCircularQueue(int k) {this->capacity = k + 1;          // 容量為 k + 1，多分配一個空間用于區分空和滿狀態this->elements = vector<int>(capacity); // 初始化數組rear = front = 0;                // 初始化隊首和隊尾指針}// 向循環隊列插入一個元素bool enQueue(int value) {if (isFull()) {return false; // 隊列已滿，插入失敗}elements[rear] = value;         // 將元素插入隊尾rear = (rear + 1) % capacity;   // 更新隊尾指針（循環）return true;}// 從循環隊列中刪除一個元素bool deQueue() {if (isEmpty()) {return false; // 隊列為空，刪除失敗}front = (front + 1) % capacity; // 更新隊首指針（循環）return true;}// 獲取隊首元素int Front() {if (isEmpty()) {return -1; // 隊列為空，返回 -1}return elements[front]; // 返回隊首元素}// 獲取隊尾元素int Rear() {if (isEmpty()) {return -1; // 隊列為空，返回 -1}return elements[(rear - 1 + capacity) % capacity]; // 返回隊尾元素（處理循環情況）}// 檢查隊列是否為空bool isEmpty() {return rear == front; // 隊首和隊尾指針相等時，隊列為空}// 檢查隊列是否已滿bool isFull() {return ((rear + 1) % capacity) == front; // 隊尾的下一個位置是隊首時，隊列已滿}
};int main() {// 創建循環隊列，容量為 3MyCircularQueue circularQueue(3);// 測試 enQueue 操作cout << "enQueue(1): " << circularQueue.enQueue(1) << endl; // 輸出: 1 (true)cout << "enQueue(2): " << circularQueue.enQueue(2) << endl; // 輸出: 1 (true)cout << "enQueue(3): " << circularQueue.enQueue(3) << endl; // 輸出: 1 (true)cout << "enQueue(4): " << circularQueue.enQueue(4) << endl; // 輸出: 0 (false，隊列已滿)// 測試 Rear 操作cout << "Rear(): " << circularQueue.Rear() << endl; // 輸出: 3// 測試 isFull 操作cout << "isFull(): " << circularQueue.isFull() << endl; // 輸出: 1 (true)// 測試 deQueue 操作cout << "deQueue(): " << circularQueue.deQueue() << endl; // 輸出: 1 (true)// 測試 enQueue 操作cout << "enQueue(4): " << circularQueue.enQueue(4) << endl; // 輸出: 1 (true)// 測試 Rear 操作cout << "Rear(): " << circularQueue.Rear() << endl; // 輸出: 4// 測試 Front 操作cout << "Front(): " << circularQueue.Front() << endl; // 輸出: 2// 測試 isEmpty 操作cout << "isEmpty(): " << circularQueue.isEmpty() << endl; // 輸出: 0 (false)return 0;
}

復雜度分析

時間復雜度：初始化和每項操作的時間復雜度均為?O(1)。
空間復雜度：O(k)，其中?k?為給定的隊列元素數目。

2.2 鏈表實現

????????我們也可以使用鏈表來實現隊列。與數組相比，鏈表實現隊列更加靈活，因為鏈表可以在 O(1)時間復雜度內完成元素的插入和刪除操作。具體來說，入隊操作是將新元素插入到鏈表的尾部，而出隊操作則是返回鏈表的頭節點，并將頭節點指向下一個節點。

循環隊列的屬性如下：

head：鏈表的頭節點，表示隊列的頭部。
tail：鏈表的尾節點，表示隊列的尾部。
capacity：隊列的容量，即隊列可以存儲的最大元素數量。
size：隊列當前存儲的元素數量。

????????通過鏈表實現循環隊列，可以避免數組實現中需要處理索引循環的問題，同時也能高效地完成隊列的基本操作。

#include <iostream>
using namespace std;// 鏈表節點定義
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};class MyCircularQueue {
private:ListNode *head;  // 隊首指針，指向鏈表的頭節點ListNode *tail;  // 隊尾指針，指向鏈表的尾節點int capacity;    // 隊列的容量int size;        // 隊列當前的大小public:// 構造函數，初始化隊列MyCircularQueue(int k) {this->capacity = k;  // 設置隊列容量this->size = 0;      // 初始化隊列大小為 0this->head = nullptr; // 初始化隊首指針為空this->tail = nullptr; // 初始化隊尾指針為空}// 向隊列尾部插入一個元素bool enQueue(int value) {if (isFull()) {return false; // 隊列已滿，插入失敗}ListNode *node = new ListNode(value); // 創建新節點if (!head) {head = tail = node; // 如果隊列為空，新節點既是隊首也是隊尾} else {tail->next = node; // 將新節點鏈接到隊尾tail = node;       // 更新隊尾指針}size++; // 隊列大小加 1return true;}// 從隊列頭部刪除一個元素bool deQueue() {if (isEmpty()) {return false; // 隊列為空，刪除失敗}ListNode *node = head; // 保存隊首節點head = head->next;     // 更新隊首指針size--;                // 隊列大小減 1delete node;           // 釋放隊首節點的內存if (isEmpty()) {tail = nullptr; // 如果隊列為空，更新隊尾指針為空}return true;}// 獲取隊首元素int Front() {if (isEmpty()) {return -1; // 隊列為空，返回 -1}return head->val; // 返回隊首節點的值}// 獲取隊尾元素int Rear() {if (isEmpty()) {return -1; // 隊列為空，返回 -1}return tail->val; // 返回隊尾節點的值}// 檢查隊列是否為空bool isEmpty() {return size == 0; // 隊列大小為 0 時為空}// 檢查隊列是否已滿bool isFull() {return size == capacity; // 隊列大小等于容量時為滿}
};int main() {// 創建循環隊列，容量為 3MyCircularQueue circularQueue(3);// 測試 enQueue 操作cout << "enQueue(1): " << circularQueue.enQueue(1) << endl; // 輸出: 1 (true)cout << "enQueue(2): " << circularQueue.enQueue(2) << endl; // 輸出: 1 (true)cout << "enQueue(3): " << circularQueue.enQueue(3) << endl; // 輸出: 1 (true)cout << "enQueue(4): " << circularQueue.enQueue(4) << endl; // 輸出: 0 (false，隊列已滿)// 測試 Rear 操作cout << "Rear(): " << circularQueue.Rear() << endl; // 輸出: 3// 測試 isFull 操作cout << "isFull(): " << circularQueue.isFull() << endl; // 輸出: 1 (true)// 測試 deQueue 操作cout << "deQueue(): " << circularQueue.deQueue() << endl; // 輸出: 1 (true)// 測試 enQueue 操作cout << "enQueue(4): " << circularQueue.enQueue(4) << endl; // 輸出: 1 (true)// 測試 Rear 操作cout << "Rear(): " << circularQueue.Rear() << endl; // 輸出: 4// 測試 Front 操作cout << "Front(): " << circularQueue.Front() << endl; // 輸出: 2// 測試 isEmpty 操作cout << "isEmpty(): " << circularQueue.isEmpty() << endl; // 輸出: 0 (false)return 0;
}

復雜度分析