循環隊列
循環隊列是一種線性數據結構，它遵循FIFO（先進先出）原則，但與普通隊列不同的是，循環隊列的最后一個元素連接回第一個元素，形成一個環形結構。這種設計有效解決了普通隊列的"假溢出"問題，可以更高效地利用存儲空間。
基本概念
1. 循環隊列特點
環形結構：隊尾連接隊首，形成循環
高效空間利用：重用出隊元素釋放的空間
兩個指針：front（隊首）和rear（隊尾）
判空判滿：需要特殊處理區分隊列空和滿的狀態
2. 基本操作
Enqueue：向隊尾添加元素
Dequeue：從隊首移除元素
Front：獲取隊首元素
Rear：獲取隊尾元素
isEmpty：判斷隊列是否為空
isFull：判斷隊列是否已滿
實際應用
CPU任務調度：循環分配CPU時間片
內存管理：循環緩沖區處理數據流
網絡數據包處理：按順序處理到達的數據包
打印機隊列：管理多個打印任務
音樂播放列表：循環播放歌曲
//數組實現(固定大小)
class CircularQueue {
private:vector<int> data;int front;int rear;int size;public:CircularQueue(int k) {data.resize(k);front = -1;rear = -1;size = k;}bool enQueue(int value) {if (isFull()) return false;if (isEmpty()) front = 0;rear = (rear + 1) % size;data[rear] = value;return true;}bool deQueue() {if (isEmpty()) return false;if (front == rear) {front = -1;rear = -1;} else {front = (front + 1) % size;}return true;}int Front() {if (isEmpty()) return -1;return data[front];}int Rear() {if (isEmpty()) return -1;return data[rear];}bool isEmpty() {return front == -1;}bool isFull() {return (rear + 1) % size == front;}
};//鏈表實現 class Node { public:int val;Node* next;Node(int value) : val(value), next(nullptr) {} };class LinkedCircularQueue { private:Node *front, *rear;public:LinkedCircularQueue() : front(nullptr), rear(nullptr) {}bool enQueue(int value) {Node* newNode = new Node(value);if (rear == nullptr) {front = rear = newNode;} else {rear->next = newNode;rear = newNode;}rear->next = front; // 形成循環return true;}bool deQueue() {if (isEmpty()) return false;int value = front->val;Node* temp = front;if (front == rear) {front = rear = nullptr;} else {front = front->next;rear->next = front; // 保持循環}delete temp;return true;}int Front() {if (isEmpty()) return -1;return front->val;}int Rear() {if (isEmpty()) return -1;return rear->val;}bool isEmpty() {return front == nullptr;}// 鏈表實現通常不考慮滿的情況（除非內存耗盡）bool isFull() {return false; } };
示例
#include <iostream>
#include <vector>using namespace std;class CircularQueue {
private:vector<int> data; // 使用vector存儲隊列元素int front; // 隊首指針int rear; // 隊尾指針int size; // 隊列容量public:// 構造函數，初始化隊列容量CircularQueue(int k) {data.resize(k); // 分配存儲空間front = -1; // 初始時隊首指針為-1表示空隊列rear = -1; // 初始時隊尾指針為-1表示空隊列size = k; // 設置隊列容量}// 入隊操作bool enQueue(int value) {if (isFull()) { // 檢查隊列是否已滿cout << "隊列已滿，無法插入 " << value << endl;return false;}if (isEmpty()) { // 如果是第一個元素front = 0; // 初始化隊首指針}rear = (rear + 1) % size; // 循環移動隊尾指針data[rear] = value; // 存儲元素cout << "插入 " << value << " 成功" << endl;return true;}// 出隊操作bool deQueue() {if (isEmpty()) { // 檢查隊列是否為空cout << "隊列為空，無法刪除" << endl;return false;}int value = data[front]; // 獲取隊首元素if (front == rear) { // 如果隊列中只有一個元素front = -1; // 重置隊首指針rear = -1; // 重置隊尾指針} else {front = (front + 1) % size; // 循環移動隊首指針}cout << "刪除 " << value << " 成功" << endl;return true;}// 獲取隊首元素int Front() {if (isEmpty()) return -1; // 隊列為空返回-1return data[front]; // 返回隊首元素}// 獲取隊尾元素int Rear() {if (isEmpty()) return -1; // 隊列為空返回-1return data[rear]; // 返回隊尾元素}// 判斷隊列是否為空bool isEmpty() {return front == -1; // 隊首指針為-1表示空隊列}// 判斷隊列是否已滿bool isFull() {return (rear + 1) % size == front; // 隊尾下一個位置是隊首表示隊列已滿}// 顯示隊列內容void display() {if (isEmpty()) { // 檢查隊列是否為空cout << "隊列為空" << endl;return;}cout << "隊列元素: ";if (rear >= front) { // 隊列元素沒有跨越數組邊界for (int i = front; i <= rear; i++)cout << data[i] << " ";} else { // 隊列元素跨越數組邊界（循環情況）for (int i = front; i < size; i++) // 打印隊首到數組末尾的元素cout << data[i] << " ";for (int i = 0; i <= rear; i++) // 打印數組開頭到隊尾的元素cout << data[i] << " ";}cout << endl;}
};int main() {// 創建容量為5的循環隊列CircularQueue q(5);// 入隊操作測試q.enQueue(1);q.enQueue(2);q.enQueue(3);q.enQueue(4);q.enQueue(5);q.enQueue(6); // 隊列已滿，無法插入// 顯示隊列內容q.display();// 出隊操作測試q.deQueue();q.deQueue();// 顯示隊列內容q.display();// 繼續入隊測試循環特性q.enQueue(6);q.enQueue(7);// 顯示隊列內容q.display();// 獲取隊首和隊尾元素cout << "隊首元素: " << q.Front() << endl;cout << "隊尾元素: " << q.Rear() << endl;return 0;
}雙向隊列
雙向隊列是一種非常實用的數據結構，它提供了比普通隊列和棧更靈活的操作方式，在算法設計和系統開發中都有廣泛應用。
一種允許在兩端進行插入和刪除操作的線性數據結構。它結合了棧和隊列的特性，提供了更靈活的數據操作方式。
基本概念
1. 雙向隊列特點
雙端操作：可以在隊首和隊尾進行插入和刪除
靈活性強：既可以作為隊列使用（FIFO），也可以作為棧使用（LIFO）
多種實現方式：可以使用數組或鏈表實現
2. 基本操作
push_front：在隊首插入元素
push_back：在隊尾插入元素
pop_front：刪除隊首元素
pop_back：刪除隊尾元素
front：獲取隊首元素
back：獲取隊尾元素
size：獲取元素數量
empty：判斷是否為空
//基與雙鏈表實現#include <iostream>
using namespace std;// 雙向鏈表節點
struct Node {int data;Node* prev;Node* next;Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};class Deque {
private:Node* front;Node* rear;int count;public:Deque() : front(nullptr), rear(nullptr), count(0) {}~Deque() {while (!empty()) {pop_front();}}// 在隊首插入void push_front(int val) {Node* newNode = new Node(val);if (empty()) {front = rear = newNode;} else {newNode->next = front;front->prev = newNode;front = newNode;}count++;}// 在隊尾插入void push_back(int val) {Node* newNode = new Node(val);if (empty()) {front = rear = newNode;} else {newNode->prev = rear;rear->next = newNode;rear = newNode;}count++;}// 刪除隊首元素void pop_front() {if (empty()) {cout << "Deque is empty!" << endl;return;}Node* temp = front;front = front->next;if (front == nullptr) {rear = nullptr;} else {front->prev = nullptr;}delete temp;count--;}// 刪除隊尾元素void pop_back() {if (empty()) {cout << "Deque is empty!" << endl;return;}Node* temp = rear;rear = rear->prev;if (rear == nullptr) {front = nullptr;} else {rear->next = nullptr;}delete temp;count--;}// 獲取隊首元素int get_front() {if (empty()) {cout << "Deque is empty!" << endl;return -1;}return front->data;}// 獲取隊尾元素int get_back() {if (empty()) {cout << "Deque is empty!" << endl;return -1;}return rear->data;}// 獲取元素數量int size() {return count;}// 判斷是否為空bool empty() {return count == 0;}// 打印隊列內容void display() {Node* current = front;cout << "Deque: [";while (current != nullptr) {cout << current->data;if (current->next != nullptr) {cout << ", ";}current = current->next;}cout << "]" << endl;}
};//基于循環數組的實現
#include <iostream>
#include <vector>
using namespace std;class ArrayDeque {
private:vector<int> data;int front;int rear;int capacity;int count;public:ArrayDeque(int k) : capacity(k), front(0), rear(0), count(0) {data.resize(k);}// 在隊首插入bool push_front(int val) {if (isFull()) {cout << "Deque is full!" << endl;return false;}front = (front - 1 + capacity) % capacity;data[front] = val;count++;return true;}// 在隊尾插入bool push_back(int val) {if (isFull()) {cout << "Deque is full!" << endl;return false;}data[rear] = val;rear = (rear + 1) % capacity;count++;return true;}// 刪除隊首元素bool pop_front() {if (isEmpty()) {cout << "Deque is empty!" << endl;return false;}front = (front + 1) % capacity;count--;return true;}// 刪除隊尾元素bool pop_back() {if (isEmpty()) {cout << "Deque is empty!" << endl;return false;}rear = (rear - 1 + capacity) % capacity;count--;return true;}// 獲取隊首元素int get_front() {if (isEmpty()) {cout << "Deque is empty!" << endl;return -1;}return data[front];}// 獲取隊尾元素int get_back() {if (isEmpty()) {cout << "Deque is empty!" << endl;return -1;}return data[(rear - 1 + capacity) % capacity];}// 判斷是否為空bool isEmpty() {return count == 0;}// 判斷是否已滿bool isFull() {return count == capacity;}// 獲取元素數量int size() {return count;}// 打印隊列內容void display() {cout << "Deque: [";for (int i = 0; i < count; i++) {cout << data[(front + i) % capacity];if (i < count - 1) {cout << ", ";}}cout << "]" << endl;}
};實際應用
撤銷操作：許多編輯器使用雙向隊列實現撤銷功能
滑動窗口：解決滑動窗口最大值等問題
任務調度：操作系統中的任務調度算法
瀏覽器歷史記錄：前進和后退功能
回文檢查：可以從兩端同時檢查字符
?示例代碼
int main() {// 測試鏈表實現的Dequecout << "Linked List Deque:" << endl;Deque dq;dq.push_back(10);dq.push_back(20);dq.push_front(5);dq.display(); // [5, 10, 20]cout << "Front: " << dq.get_front() << endl; // 5cout << "Back: " << dq.get_back() << endl; // 20dq.pop_front();dq.display(); // [10, 20]dq.pop_back();dq.display(); // [10]// 測試數組實現的Dequecout << "\nArray Deque:" << endl;ArrayDeque adq(5);adq.push_back(100);adq.push_front(50);adq.push_back(200);adq.display(); // [50, 100, 200]cout << "Front: " << adq.get_front() << endl; // 50cout << "Back: " << adq.get_back() << endl; // 200adq.pop_front();adq.display(); // [100, 200]adq.pop_back();adq.display(); // [100]return 0;
}單調隊列
單調隊列是一種特殊的隊列數據結構，它保持隊列中元素的單調性（單調遞增或單調遞減）。這種數據結構常用于解決滑動窗口相關問題，能夠高效地獲取窗口中的最大值或最小值。
單調隊列通過維護數據的單調性，將原本O(nk)的滑動窗口問題優化到O(n)，是解決一類極值問題的有效工具。掌握其核心思想和實現技巧對算法能力提升有很大幫助
基本概念
1. 單調隊列特性
單調性：隊列中元素保持單調遞增或單調遞減
雙端操作：可以從隊首和隊尾進行插入和刪除
高效性：能在O(1)時間內獲取當前窗口的最大值/最小值
2. 常見應用場景
滑動窗口最大值/最小值
股票價格分析
數據流中的極值問題
動態規劃優化
//單調遞減隊列 用于求滑動窗口最大值）#include <deque>
#include <vector>using namespace std;class MonotonicQueue {
private:deque<int> data; // 存儲元素的下標public:// 在隊尾添加元素，維護單調遞減性void push(int idx, const vector<int>& nums) {while (!data.empty() && nums[data.back()] <= nums[idx]) {data.pop_back(); // 移除比當前元素小的元素}data.push_back(idx);}// 獲取當前隊列最大值（隊首元素）int max() {return data.front();}// 移除超出窗口范圍的元素void pop(int idx) {while (!data.empty() && data.front() <= idx) {data.pop_front();}}// 判斷隊列是否為空bool empty() {return data.empty();}
};vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;MonotonicQueue mq;// 初始化第一個窗口for (int i = 0; i < k; ++i) {mq.push(i, nums);}result.push_back(nums[mq.max()]);// 滑動窗口for (int i = k; i < nums.size(); ++i) {mq.pop(i - k); // 移除離開窗口的元素mq.push(i, nums); // 添加新元素result.push_back(nums[mq.max()]);}return result;
}//單調遞增隊列 用于求滑動窗口最小值）
class MonotonicQueueMin {
private:deque<int> data; // 存儲元素的下標public:void push(int idx, const vector<int>& nums) {while (!data.empty() && nums[data.back()] >= nums[idx]) {data.pop_back(); // 移除比當前元素大的元素}data.push_back(idx);}int min() {return data.front();}void pop(int idx) {while (!data.empty() && data.front() <= idx) {data.pop_front();}}bool empty() {return data.empty();}
};vector<int> minSlidingWindow(vector<int>& nums, int k) {vector<int> result;MonotonicQueueMin mq;for (int i = 0; i < k; ++i) {mq.push(i, nums);}result.push_back(nums[mq.min()]);for (int i = k; i < nums.size(); ++i) {mq.pop(i - k);mq.push(i, nums);result.push_back(nums[mq.min()]);}return result;
}經典應用
//滑動窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;deque<int> dq; // 存儲下標for (int i = 0; i < nums.size(); ++i) {// 移除超出窗口范圍的元素while (!dq.empty() && dq.front() <= i - k) {dq.pop_front();}// 維護單調遞減性while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}dq.push_back(i);// 窗口形成后開始記錄結果if (i >= k - 1) {res.push_back(nums[dq.front()]);}}return res;
}//隊列的最大值class MaxQueue {
private:queue<int> data;deque<int> max_q;public:MaxQueue() {}int max_value() {if (max_q.empty()) return -1;return max_q.front();}void push_back(int value) {data.push(value);while (!max_q.empty() && max_q.back() < value) {max_q.pop_back();}max_q.push_back(value);}int pop_front() {if (data.empty()) return -1;int val = data.front();data.pop();if (val == max_q.front()) {max_q.pop_front();}return val;}
};//股票的價格跨度
class StockSpanner {
private:stack<pair<int, int>> st; // {price, span}public:StockSpanner() {}int next(int price) {int span = 1;while (!st.empty() && st.top().first <= price) {span += st.top().second;st.pop();}st.push({price, span});return span;}
};
)
