C++双端队列知识点+习题

        在C++中，双端队列（Deque，发音为“deck”）是标准模板库（STL）中的一种容器适配器，其全称为Double-Ended Queue。它结合了队列和栈的特点，允许在容器的两端（前端和后端）进行高效的插入和删除操作。std::deque是C++ STL中实现双端队列的具体类模板，它提供了丰富的成员函数和操作接口，使其在多种场景下都非常有用。

一、 C++双端队列知识点

1. std::deque的基本特性

• 两端操作：可以在容器的前端（front）和后端（back）进行插入、删除和访问操作。

• 随机访问：支持通过索引访问元素，类似于数组或std::vector。

• 动态扩展：与std::vector类似，std::deque可以根据需要动态扩展内存，但它的扩展机制更复杂，因为它需要同时管理两端的内存。

• 内存管理：std::deque内部通常使用多个固定大小的内存块（称为“缓冲区”）来存储元素。这种设计使得两端操作的效率很高，但随机访问的效率略低于std::vector。

2. std::deque的构造和初始化

std::deque可以通过多种方式构造：

• 默认构造：创建一个空的双端队列。

• 指定大小和默认值：创建一个具有指定大小的双端队列，并用默认值填充。

• 初始化列表：使用初始化列表直接构造双端队列。

• 从另一个容器复制或移动构造。

#include <deque>
#include <iostream>int main() {// 默认构造std::deque<int> dq1;// 指定大小和默认值std::deque<int> dq2(5, 10); // 5个元素，每个值为10// 初始化列表std::deque<int> dq3 = {1, 2, 3, 4, 5};// 从另一个容器复制构造std::deque<int> dq4(dq3);std::cout << "dq1 size: " << dq1.size() << std::endl;std::cout << "dq2: ";for (int x : dq2) {std::cout << x << " ";}std::cout << "\ndq3: ";for (int x : dq3) {std::cout << x << " ";}std::cout << "\ndq4: ";for (int x : dq4) {std::cout << x << " ";}std::cout << std::endl;return 0;
}

3. 常用操作

3.1 插入操作

• 前端插入：push_front()，在容器前端插入一个元素。

• 后端插入：push_back()，在容器后端插入一个元素。

• 指定位置插入：insert()，可以在任意位置插入一个或多个元素。

#include <deque>
#include <iostream>int main() {std::deque<int> dq = {1, 2, 3};// 前端插入dq.push_front(0);// 后端插入dq.push_back(4);std::cout << "Deque after insertions: ";for (int x : dq) {std::cout << x << " ";}std::cout << std::endl;// 指定位置插入auto it = dq.begin() + 2; // 指向索引2的位置dq.insert(it, 10);        // 在索引2的位置插入10std::cout << "Deque after insertion at position: ";for (int x : dq) {std::cout << x << " ";}std::cout << std::endl;return 0;
}

3.2 删除操作

• 前端删除：pop_front()，删除容器前端的元素。

• 后端删除：pop_back()，删除容器后端的元素。

• 指定位置删除：erase()，删除任意位置的元素。

#include <deque>
#include <iostream>int main() {std::deque<int> dq = {0, 1, 10, 2, 3, 4};// 前端删除dq.pop_front();// 后端删除dq.pop_back();std::cout << "Deque after deletions: ";for (int x : dq) {std::cout << x << " ";}std::cout << std::endl;// 指定位置删除auto it = dq.begin() + 2; // 指向索引2的位置dq.erase(it);             // 删除索引2的元素std::cout << "Deque after erasing at position: ";for (int x : dq) {std::cout << x << " ";}std::cout << std::endl;return 0;
}

3.3 访问操作

• 访问前端元素：front()，返回前端元素的引用。

• 访问后端元素：back()，返回后端元素的引用。

• 通过索引访问：operator[] 或 at()，支持随机访问。

#include <deque>
#include <iostream>int main() {std::deque<int> dq = {0, 1, 2, 3, 4};std::cout << "Front element: " << dq.front() << std::endl;std::cout << "Back element: " << dq.back() << std::endl;// 通过索引访问std::cout << "Element at index 2: " << dq[2] << std::endl;std::cout << "Element at index 3 (using at()): " << dq.at(3) << std::endl;return 0;
}

3.4 其他操作

• 清空容器：clear()，删除所有元素。

• 检查是否为空：empty()，判断容器是否为空。

• 获取大小：size()，返回容器中元素的数量。

• 交换内容：swap()，与另一个std::deque交换内容。

#include <deque>
#include <iostream>int main() {std::deque<int> dq = {0, 1, 2, 3, 4};std::cout << "Is deque empty? " << (dq.empty() ? "Yes" : "No") << std::endl;std::cout << "Size of deque: " << dq.size() << std::endl;// 清空容器dq.clear();std::cout << "Deque size after clear: " << dq.size() << std::endl;// 交换内容std::deque<int> dq2 = {10, 20, 30};dq.swap(dq2);std::cout << "Deque after swap: ";for (int x : dq) {std::cout << x << " ";}std::cout << std::endl;return 0;
}

4. 迭代器支持

std::deque支持双向迭代器，可以使用begin()、end()、rbegin()和rend()等方法获取迭代器，并通过迭代器进行遍历、插入和删除操作。

#include <deque>
#include <iostream>int main() {std::deque<int> dq = {0, 1, 2, 3, 4};// 使用迭代器遍历for (auto it = dq.begin(); it != dq.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用范围for循环for (int x : dq) {std::cout << x << " ";}std::cout << std::endl;// 使用反向迭代器for (auto it = dq.rbegin(); it != dq.rend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

5. 内存管理

std::deque的内存管理机制使其在两端操作时非常高效：

• 它内部使用多个固定大小的内存块（缓冲区）来存储元素。

• 每个缓冲区的大小通常与机器的页面大小（如4KB）对齐，以减少内存碎片。

• 插入和删除操作通常只需要在缓冲区的头部或尾部进行，而不需要像std::vector那样频繁地重新分配整个内存。

这种设计使得std::deque在以下场景中非常有用：

1. 需要频繁在两端插入和删除元素：如滑动窗口问题、任务调度等。

2. 需要随机访问但又不希望像std::vector那样频繁重新分配内存。

6. 使用场景

6.1 滑动窗口问题

std::deque常用于解决滑动窗口的最大值或最小值问题。通过维护一个单调队列，可以在O(1)时间内获取窗口内的最大值或最小值。

#include <deque>
#include <iostream>
#include <vector>std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {std::deque<int> dq; // 存储索引std::vector<int> result;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) {result.push_back(nums[dq.front()]);}}return result;
}int main() {std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};int k = 3;std::vector<int> result = maxSlidingWindow(nums, k);std::cout << "Max sliding window: ";for (int x : result) {std::cout << x << " ";}std::cout << std::endl;return 0;
}

6.2 回文检查

std::deque可以用于检查字符串或序列是否为回文。通过从两端同时读取元素，可以快速判断是否对称。

#include <deque>
#include <iostream>bool isPalindrome(const std::string& str) {std::deque<char> dq(str.begin(), str.end());while (dq.size() > 1) {if (dq.front() != dq.back()) {return false;}dq.pop_front();dq.pop_back();}return true;
}int main() {std::string str = "racecar";std::cout << str << " is palindrome? " << (isPalindrome(str) ? "Yes" : "No") << std::endl;return 0;
}

7. 性能对比

• 与std::vector对比：

  • std::vector更适合随机访问，但在两端插入和删除时效率较低（尤其是前端操作）。

  • std::deque在两端操作时效率更高，但随机访问的效率略低于std::vector。

• 与std::list对比：

  • std::list支持在任意位置高效插入和删除，但不支持随机访问。

  • std::deque支持随机访问，且在两端操作时效率更高。

8. 总结

std::deque是C++ STL中一个非常强大且灵活的容器，适用于需要在两端频繁操作的场景。它结合了队列和栈的特点，同时支持随机访问，具有较高的通用性和效率。通过合理使用std::deque，可以简化代码逻辑并提高程序性能。

二、练习 

例一、Problem - 6375

#include <deque>
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;int main()
{int n, q; // n表示队列的数量，q表示操作的数量while (scanf("%d%d", &n, &q) != EOF) // 读取n和q，直到文件结束{deque<int> deq[n + 1]; // 创建n+1个双端队列（索引从0到n）for (int i = 0; i < q; i++) // 对每个操作进行循环{int a, u, w;scanf("%d%d%d", &a, &u, &w); // 读取操作类型a，以及参数u和wif (a == 1) // 如果操作类型是1，则执行插入操作{int value;scanf("%d", &value); // 读取要插入的值if (w == 0) // 根据w的值决定在队首还是队尾插入{deq[u].push_front(value); // 在队首插入}else {deq[u].push_back(value); // 在队尾插入}}else if (a == 2) // 如果操作类型是2，则执行查询并删除操作{if (!deq[u].empty()) // 确保队列非空{if (w == 0) // 根据w的值决定查询并删除队首还是队尾元素{printf("%d\n", deq[u][0]); // 打印队首元素deq[u].pop_front(); // 删除队首元素}else{printf("%d\n", deq[u].back()); // 打印队尾元素deq[u].pop_back(); // 删除队尾元素}}else {printf("-1\n"); // 如果队列为空，打印-1}}else // 操作类型为3时，先交换w和v的含义，然后根据w决定是否翻转队列v，并将v的所有元素移动到队列u中{int v = w; // 注意这里先读入的是v的实际值，即原先的wscanf("%d", &w); // 再次读取w的真实值if (w == 1 && deq[v].size() >= 2) // 如果需要翻转且队列v至少有两个元素{reverse(deq[v].begin(), deq[v].end()); // 翻转队列v}while (!deq[v].empty()) // 将队列v的所有元素移动到队列u{deq[u].push_back(deq[v].front()); // 把队列v的队首元素添加到队列u的队尾deq[v].pop_front(); // 移除队列v的队首元素}}}}return 0;
}

例二、 641. 设计循环双端队列 - 力扣（LeetCode）

设计实现双端队列。

实现 MyCircularDeque 类:

• MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
• boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
• boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
• boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
• boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
• int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
• int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
• boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
• boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4

提示：

• 1 <= k <= 1000
• 0 <= value <= 1000
• insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull  调用次数不大于 2000 次

class MyCircularDeque {
private:vector<int> elements;int rear, front;int capacity;public:MyCircularDeque(int k) {capacity = k + 1;rear = front = 0;elements = vector<int>(k + 1);}bool insertFront(int value) {if (isFull()) {return false;}front = (front - 1 + capacity) % capacity;elements[front] = value;return true;}bool insertLast(int value) {if (isFull()) {return false;}elements[rear] = value;rear = (rear + 1) % capacity;return true;}bool deleteFront() {if (isEmpty()) {return false;}front = (front + 1) % capacity;return true;}bool deleteLast() {if (isEmpty()) {return false;}rear = (rear - 1 + capacity) % capacity;return true;}int getFront() {if (isEmpty()) {return -1;}return elements[front];}int getRear() {if (isEmpty()) {return -1;}return elements[(rear - 1 + capacity) % capacity];}   bool isEmpty() {return rear == front;}bool isFull() {return (rear + 1) % capacity == front;}
};