循环队列
循环队列是一种线性数据结构，它遵循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;}
};
)
