网站开发的源码,杭州科技网站,手机企业网站,网站版面布局循环队列 循环队列是一种线性数据结构#xff0c;它遵循FIFO#xff08;先进先出#xff09;原则#xff0c;但与普通队列不同的是#xff0c;循环队列的最后一个元素连接回第一个元素#xff0c;形成一个环形结构。这种设计有效解决了普通队列的假溢出问题它遵循FIFO先进先出原则但与普通队列不同的是循环队列的最后一个元素连接回第一个元素形成一个环形结构。这种设计有效解决了普通队列的假溢出问题可以更高效地利用存储空间。 基本概念 1. 循环队列特点 环形结构队尾连接队首形成循环 高效空间利用重用出队元素释放的空间 两个指针front队首和rear队尾 判空判满需要特殊处理区分队列空和满的状态 2. 基本操作 Enqueue向队尾添加元素 Dequeue从队首移除元素 Front获取队首元素 Rear获取队尾元素 isEmpty判断队列是否为空 isFull判断队列是否已满 实际应用 CPU任务调度循环分配CPU时间片 内存管理循环缓冲区处理数据流 网络数据包处理按顺序处理到达的数据包 打印机队列管理多个打印任务 音乐播放列表循环播放歌曲 //数组实现(固定大小)
class CircularQueue {
private:vectorint 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 vectorusing namespace std;class CircularQueue {
private:vectorint 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:vectorint 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 vectorusing namespace std;class MonotonicQueue {
private:dequeint data; // 存储元素的下标public:// 在队尾添加元素维护单调递减性void push(int idx, const vectorint 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();}
};vectorint maxSlidingWindow(vectorint nums, int k) {vectorint 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:dequeint data; // 存储元素的下标public:void push(int idx, const vectorint 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();}
};vectorint minSlidingWindow(vectorint nums, int k) {vectorint 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;
}
经典应用
//滑动窗口最大值
vectorint maxSlidingWindow(vectorint nums, int k) {vectorint res;dequeint 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:queueint data;dequeint 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:stackpairint, 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;}
};
