deque双端队列详解
极难6语言版本：通用
概述：像两端都可以开门的通道，deque支持在开头和结尾快速插入删除，是双端操作的利器。
deque双端队列：两端都能快速进出的超级队列
开场白：这是什么神奇队列？
你见过那种两边都能开门的地铁车厢吗？乘客可以从左边门上车，也可以从右边门下车，非常灵活。在编程中，也有这样一种容器，它允许你在开头和结尾都以极快的速度添加或删除元素——这就是 deque（读作“deck”），全称 double-ended queue（双端队列）。
想象一下你的零食盒：你可以从前面拿刚买的薯片，也可以从后面塞进新买的糖果，两头都能操作。当你只从一头操作时，它就像普通的队列或栈；但当你需要两头操作时，它就是你的最佳选择。
如果你学过 vector（动态数组）和 list（链表），那么 deque 就像它们的“合体版”：既有 vector 的随机访问能力，又有 list 的前后快速插入能力（但中间插入还是慢）。接下来我们就一步步揭开它的神秘面纱。
一、deque 的核心特点
- 两端快速插入/删除：
push_front（头插）、pop_front（头删）、push_back（尾插）、pop_back（尾删）的时间都是 O(1)，超级快。 - 随机访问：可以通过
[索引]或at(索引)直接访问任意位置的元素，也是 O(1)，但比vector稍慢一点点（因为内部需要多一次跳转）。 - 逻辑连续：看起来像一条完整的队伍，但实际上底层由多块小内存（缓冲区）拼接而成。这样，在两端添加新元素时，只需要分配新的小块，不用像
vector那样把整条队伍的人全部往后搬。 - 没有 reserve：
deque不需要像vector那样提前预留空间，因为它是按需分配小块的。
生活中的对照：
- 学校的值日安排：你可以在周一早上把新同学安排到队首，也可以在周五下午把表现不好的同学放到队尾。
- 游戏的技能快捷键：你可以把紧急技能（如回血）放在技能栏最左边（头），普通技能放在右边（尾），随时可以在两头调整。
二、常见操作与语法（C++）
1. 头文件与创建
#include <deque> // 使用deque需要包含头文件
deque<int> dq; // 创建一个空的int型双端队列
deque<string> names(5); // 创建包含5个空字符串的双端队列
deque<double> scores(3, 0.0); // 创建3个0.0的双端队列
2. 添加元素
dq.push_back(10); // 在尾部添加10
dq.push_front(20); // 在头部添加20
dq.push_back(30); // 现在队列为：20, 10, 30
注意：没有 insert 的演示？其实 deque 也有 insert 可以在中间插入，但速度很慢（O(n)），所以很少用。我们重点掌握头尾操作。
3. 删除元素
dq.pop_back(); // 删除尾部元素（30），剩下20,10
dq.pop_front(); // 删除头部元素（20），剩下10
小心：如果队列是空的，调用 pop_back 或 pop_front 会导致程序崩溃（未定义行为），所以要先用 empty() 判断。
4. 访问元素
int first = dq.front(); // 返回第一个元素（不删除）
int last = dq.back(); // 返回最后一个元素
int pos = dq[0]; // 通过下标访问，不检查越界
int safe = dq.at(0); // 通过at访问，越界会抛出异常
5. 大小与清空
int n = dq.size(); // 返回元素个数
bool empty = dq.empty(); // 是否为空
dq.clear(); // 清空所有元素
dq.resize(10); // 调整为10个元素，如果变长则用默认值填充
三、内部原理（用“教室”比喻）
很多同学问：为什么 deque 两端操作这么快？我们来打个比方。
想象你有一排教室（缓冲区），每个教室里有固定数量的座位（比如4个座位）。这些教室之间通过一条**走廊（中控数组）**连接。当你要在队伍头部插入一个人时：
- 如果头部的教室还有空座位，直接坐进去，O(1)。
- 如果头部的教室满了，就在走廊最前面接一个新教室，让人坐进去，也是O(1)。
当你要随机访问第5个人时：
- 先通过走廊找到是第几个教室（比如第2个教室）。
- 再在该教室里找到具体的座位（比如座位1）。 所以比直接在一个大教室（vector）里找多了一步，但还是很快。
而 vector 则像一个大礼堂，所有人必须按顺序坐。如果在最前面加一个人，所有人都要往后挪一个位置，非常慢（O(n)）。但 vector 的随机访问就像直接报座位号，一步到位，超级快。
所以 deque 在两端操作上完胜 vector，在随机访问上稍逊一筹，但在中间插入上两者都很慢（都要搬动很多元素）。
四、常见错误（新手必看）
错误1：在中间频繁插入（以为和list一样快）
deque<int> dq = {1,2,3,4,5};
for (int i = 0; i < 100000; i++) {
dq.insert(dq.begin() + dq.size()/2, i); // 每次都在中间插入
}
后果：每次插入都需要移动一半的元素，慢到爆炸。如果你需要频繁在中间插入，请使用 list。
错误2：对空deque调用pop_front或pop_back
deque<int> empty;
empty.pop_front(); // 崩溃！因为队列为空
正确做法：先判断 if (!empty.empty()) empty.pop_front();
错误3：把deque当作vector来reserve
deque<int> dq;
dq.reserve(100); // 编译错误！deque没有reserve函数
因为 deque 不需要预先分配连续空间，所以没有 reserve。
错误4：误以为deque的随机访问和vector一样快
虽然都是O(1)，但 deque 的常数更大。如果你要写一个需要超级大量随机访问的程序（比如图形处理），vector 更合适。
错误5：在Python中使用list当双端队列
queue = []
queue.insert(0, "小明") # 头部插入，list是O(n)
queue.pop(0) # 头部删除，list是O(n)
正确做法：使用 collections.deque。
五、完整可运行示例（C++）
下面是一个完整的程序，用“电影院卖爆米花”的场景，展示 deque 的各种操作。每一行变量定义都加了中文注释。
#include <iostream>
#include <deque> // 双端队列头文件
#include <algorithm> // sort函数
#include <string> // string类型
using namespace std;
int main() {
// 创建一个双端队列，存放顾客的名字（string类型）
deque<string> customer_queue;
// 尾部添加：三个人依次买爆米花
customer_queue.push_back("小明");
customer_queue.push_back("小红");
customer_queue.push_back("小刚");
cout << "初始排队顺序: ";
for (const string& name : customer_queue) cout << name << " ";
cout << endl;
// 头部插队：小明妈妈来了，要求排到最前面
customer_queue.push_front("小明妈妈");
cout << "小明妈妈插队后: ";
for (const string& name : customer_queue) cout << name << " ";
cout << endl;
// 访问队头和队尾
cout << "现在队头是: " << customer_queue.front() << endl; // 小明妈妈
cout << "队尾是: " << customer_queue.back() << endl; // 小刚
// 队头离开（小明妈妈买完走了）
customer_queue.pop_front();
cout << "小明妈妈离开后队头变成: " << customer_queue.front() << endl; // 小明
// 队尾离开（小刚等不及走了）
customer_queue.pop_back();
cout << "小刚离开后队尾变成: " << customer_queue.back() << endl; // 小红
// 随机访问：通过下标获取第二个人（索引1）
cout << "现在队列中第2个人是: " << customer_queue[1] << endl; // 现在只有小明(0)和小红(1)，所以是小红
// 使用at安全访问（越界会抛出异常）
try {
cout << "尝试访问索引5（越界）: " << customer_queue.at(5) << endl;
} catch (const out_of_range& e) {
cout << "访问越界, 异常信息: " << e.what() << endl;
}
// 修改元素：把小明改名为“大明”
customer_queue[0] = "大明";
cout << "修改后队列为: ";
for (const string& name : customer_queue) cout << name << " ";
cout << endl;
// 清空队列
customer_queue.clear();
cout << "清空后队列大小: " << customer_queue.size() << endl; // 0
// ---------- 下面用整数演示排序 ----------
// 创建一个整型双端队列
deque<int> score_queue;
score_queue.push_back(85); // 尾部添加85
score_queue.push_back(92); // 尾部添加92
score_queue.push_front(78); // 头部添加78
score_queue.push_front(88); // 头部添加88
// 现在队列: 88, 78, 85, 92
cout << "排序前数字: ";
for (int v : score_queue) cout << v << " ";
cout << endl;
// 排序：deque的迭代器是随机访问迭代器，可以直接用sort
sort(score_queue.begin(), score_queue.end());
cout << "排序后数字: ";
for (int v : score_queue) cout << v << " ";
cout << endl;
return 0;
}
运行结果：
初始排队顺序: 小明 小红 小刚
小明妈妈插队后: 小明妈妈 小明 小红 小刚
现在队头是: 小明妈妈
队尾是: 小刚
小明妈妈离开后队头变成: 小明
小刚离开后队尾变成: 小红
现在队列中第2个人是: 小红
访问越界, 异常信息: deque::_M_range_check: __n (which is 5) >= this->size() (which is 2)
修改后队列为: 大明 小红
清空后队列大小: 0
排序前数字: 88 78 85 92
排序后数字: 78 85 88 92
六、Python中的双端队列（collections.deque）
Python标准库的 collections.deque 和C++的 deque 几乎一模一样，也是两端O(1)操作。下面是对应的代码，每行也有中文注释：
from collections import deque
# 创建一个空双端队列，存放顾客名字
customer_queue = deque()
# 尾部添加
customer_queue.append("小明")
customer_queue.append("小红")
customer_queue.append("小刚")
print("初始排队顺序:", list(customer_queue))
# 头部插队
customer_queue.appendleft("小明妈妈")
print("小明妈妈插队后:", list(customer_queue))
# 访问队头和队尾（用索引0和-1）
print("队头:", customer_queue[0]) # 小明妈妈
print("队尾:", customer_queue[-1]) # 小刚
# 头部离开
customer_queue.popleft()
print("小明妈妈离开后队头:", customer_queue[0]) # 小明
# 尾部离开
customer_queue.pop()
print("小刚离开后队尾:", customer_queue[-1]) # 小红
# 随机访问：通过索引
print("第2个人:", customer_queue[1]) # 现在只有小明(0)和小红(1)，所以是小红
# 修改元素
customer_queue[0] = "大明"
print("修改后队列:", list(customer_queue))
# 清空
customer_queue.clear()
print("清空后长度:", len(customer_queue))
# ---------- 整数排序演示 ----------
score_queue = deque()
score_queue.append(85)
score_queue.append(92)
score_queue.appendleft(78)
score_queue.appendleft(88)
print("排序前:", list(score_queue)) # [88, 78, 85, 92]
# 排序：deque没有sort方法，需要转成list排序再转回deque
sorted_scores = deque(sorted(score_queue))
print("排序后:", list(sorted_scores)) # [78, 85, 88, 92]
Python的特别提醒：
deque也支持rotate(n)方法，可以把元素循环左移或右移，比如dq.rotate(1)相当于把最后一个元素放到开头。C++的deque没有这个功能。- 虽然
deque支持通过索引随机访问，但底层也是分段存储，速度比list慢一点点（但差别不大，一般场景感觉不到）。 - 不要用
list来模拟双端队列的头插头删，因为list是数组，头部插入是O(n)。
七、实战应用：滑动窗口最大值
这是一个很经典的算法题，特别适合用 deque 解决。比如你有一串数字，要找出每个长度为k的子数组中的最大值。用 deque 维护窗口内可能有用的索引，效率超级高。
（这里简单提一下，不展开代码，作为相关指引）
八、总结与相关指引
什么时候该用deque？
- 双端操作频繁：比如任务队列，紧急任务插队到队头，普通任务放到队尾。
- 需要偶尔随机访问：比如要查看队伍中第几个人的名字。
- 不需要在中间插入/删除：如果中间操作很多，用
list更好。 - 不想预先分配空间：
deque不需要reserve。
和vector、list的对比
| 操作 | deque | vector | list |
|---|---|---|---|
| 头插/头删 | O(1) | O(n) | O(1) |
| 尾插/尾删 | O(1) | 均摊O(1) | O(1) |
| 随机访问 | O(1)（稍慢） | O(1) | O(n) |
| 中间插入 | O(n) | O(n) | O(1)（需先找到位置） |
| 内存占用 | 中 | 小（连续） | 大（每个节点额外指针） |
你还可以学习
- stack和queue：它们都是基于
deque的容器适配器（默认底层就是deque），所以如果你只需要栈或队列的功能，直接用它们更简单。 - priority_queue：优先级队列，底层是堆，适合需要按优先级取出的场景。
- 算法题中的滑动窗口：这是deque的经典应用。
现在你已经完全掌握了双端队列！下次写程序时，如果需要两头操作，别犹豫，直接用 deque 吧。它就像你的多功能工具箱，随手可得，又快又方便。
例题精讲
1单选题
关于std::deque的迭代器失效问题，以下说法正确的是？
A在deque头部插入元素后，所有迭代器仍然有效。
B在deque尾部插入元素后，所有引用和指针失效。
C在deque中间插入元素后，只有指向插入位置之后元素的迭代器失效。
D在deque中间插入元素后，所有迭代器、引用和指针都失效。
2单选题
关于std::deque与std::vector的随机访问性能，以下说法正确的是？
Adeque的operator[]与vector一样快，因为都是常数时间。
Bdeque的operator[]比vector慢，因为deque需要两次指针解引用。
Cdeque的operator[]比vector慢，因为deque是链表结构。
Ddeque不支持随机访问。
3判断题
在使用deque的push_back操作时，如果deque的当前容量不足以容纳新元素，则deque会像vector一样重新分配更大的内存空间并将所有元素复制到新内存中。
4填空题
使用deque实现一个函数，移除deque中所有偶数元素。补全代码：
void removeEven(std::deque<int>& dq) {
auto new_end = std::remove_if(dq.begin(), dq.end(), [](int x) { return x % 2 == 0; });
dq.____(new_end, dq.end());
}5填空题
给定一个deque<int> dq = {1,2,3,4,5}，要求循环左移2位（即前2个元素移到尾部，结果为{3,4,5,1,2}）。补全代码：
std::deque<int> dq = {1,2,3,4,5};
int k = 2;
____(dq.begin(), dq.begin() + k, dq.end());
// 此时 dq 为 {3,4,5,1,2}