本课时有配套视频讲解，购买后即可观看（永久有效）
双端队列
一、课上练习
编程练习
二、知识总结
✨ 核心思想
双端队列（Deque, Double-Ended Queue）是一种允许在两端进行插入和删除操作的数据结构。与普通队列（只能尾部入队、头部出队）不同，deque 的头部和尾部都可以进行 O(1) 的插入和删除。
C++ STL 的 deque 底层使用分段连续存储（多个固定大小的数组块），同时支持 O(1) 随机访问。
✨ STL deque 操作
deque 基本操作
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 deque<int> dq;
6
7 // 尾部操作
8 dq.push_back(1); // [1]
9 dq.push_back(2); // [1, 2]
10 dq.push_back(3); // [1, 2, 3]
11
12 // 头部操作
13 dq.push_front(0); // [0, 1, 2, 3]
14 dq.push_front(-1); // [-1, 0, 1, 2, 3]
15
16 // 随机访问 O(1)
17 cout << "dq[2] = " << dq[2] << endl; // 1
18
19 // 头尾访问
20 cout << "front = " << dq.front() << endl; // -1
21 cout << "back = " << dq.back() << endl; // 3
22
23 // 头尾删除
24 dq.pop_front(); // [0, 1, 2, 3]
25 dq.pop_back(); // [0, 1, 2]
26
27 // 大小
28 cout << "size = " << dq.size() << endl; // 3
29
30 // 遍历
31 for (int x : dq) cout << x << " "; // 0 1 2
32 cout << endl;
33
34 return 0;
35}✨ deque vs vector vs list
| 操作 | deque | vector | list |
|---|---|---|---|
| push_back | O(1) | 均摊 O(1) | O(1) |
| push_front | O(1) | O(n) | O(1) |
| pop_back | O(1) | O(1) | O(1) |
| pop_front | O(1) | O(n) | O(1) |
| 随机访问 [i] | O(1) | O(1) | O(n) |
| 中间插入 | O(n) | O(n) | O(1) |
| 内存布局 | 分段连续 | 连续 | 链表 |
何时选择 deque：需要头尾都能高效操作，同时又需要随机访问时。
✨ 经典应用：滑动窗口
双端队列最重要的应用是滑动窗口问题。虽然这个场景更常用"单调队列"（后面会学），但理解 deque 的基本操作是前提。
问题：给定数组和窗口大小 k，求每个窗口中的最大值。
滑动窗口最大值（暴力 vs deque）
1#include <bits/stdc++.h>
2using namespace std;
3
4// 暴力法 O(nk)
5void bruteForce(int a[], int n, int k) {
6 for (int i = 0; i <= n - k; i++) {
7 int maxVal = a[i];
8 for (int j = i + 1; j < i + k; j++)
9 maxVal = max(maxVal, a[j]);
10 printf("%d ", maxVal);
11 }
12 printf("\n");
13}
14
15// 单调队列法 O(n) — 详见"单调队列"一课
16void dequeMethod(int a[], int n, int k) {
17 deque<int> dq; // 存储下标，维护一个递减队列
18
19 for (int i = 0; i < n; i++) {
20 // 移除超出窗口范围的元素
21 while (!dq.empty() && dq.front() <= i - k)
22 dq.pop_front();
23
24 // 维护单调性：移除所有比 a[i] 小的元素
25 while (!dq.empty() && a[dq.back()] <= a[i])
26 dq.pop_back();
27
28 dq.push_back(i);
29
30 // 输出窗口最大值
31 if (i >= k - 1)
32 printf("%d ", a[dq.front()]);
33 }
34 printf("\n");
35}
36
37int main() {
38 int a[] = {1, 3, -1, -3, 5, 3, 6, 7};
39 int n = 8, k = 3;
40
41 printf("暴力法: ");
42 bruteForce(a, n, k);
43
44 printf("deque法: ");
45 dequeMethod(a, n, k);
46
47 return 0;
48}✨ 执行示例
以数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小 k=3 为例：
| i | a[i] | deque 中的下标 | deque 中对应的值 | 窗口最大值 |
|---|---|---|---|---|
| 0 | 1 | [0] | [1] | - |
| 1 | 3 | [1] | [3] | - |
| 2 | -1 | [1, 2] | [3, -1] | 3 |
| 3 | -3 | [1, 2, 3] | [3, -1, -3] | 3 |
| 4 | 5 | [4] | [5] | 5 |
| 5 | 3 | [4, 5] | [5, 3] | 5 |
| 6 | 6 | [6] | [6] | 6 |
| 7 | 7 | [7] | [7] | 7 |
输出：3 3 5 5 6 7
关键步骤分析（以 i=4, a[i]=5 为例）：
- 检查队首：dq.front()=1，
1 <= 4-3=1，移除（超出窗口） - 检查队尾：a[dq.back()]=a[3]=-3
<= 5，移除 - 检查队尾：a[dq.back()]=a[2]=-1
<= 5，移除 - deque 为空，push_back(4)
- 窗口最大值 = a[dq.front()] = a[4] = 5
✨ BFS 中的双端队列（0-1 BFS）
当边权只有 0 和 1 时，可以用 deque 代替优先队列做最短路，时间复杂度从 O(E log V) 降到 O(V + E)：
0-1 BFS
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5vector<pair<int, int>> adj[MAXN]; // (邻居, 边权 0 或 1)
6int dist[MAXN];
7
8void bfs01(int start, int n) {
9 fill(dist, dist + n + 1, INT_MAX);
10 dist[start] = 0;
11 deque<int> dq;
12 dq.push_back(start);
13
14 while (!dq.empty()) {
15 int u = dq.front();
16 dq.pop_front();
17
18 for (auto [v, w] : adj[u]) {
19 if (dist[u] + w < dist[v]) {
20 dist[v] = dist[u] + w;
21 if (w == 0)
22 dq.push_front(v); // 权为 0，加到队首
23 else
24 dq.push_back(v); // 权为 1，加到队尾
25 }
26 }
27 }
28}✨ 解题步骤详解
遇到以下情况时考虑使用 deque：
- 需要头尾都能操作：同时需要 pushfront 和 pushback
- 滑动窗口问题：维护窗口内的最大/最小值（配合单调性）
- 0-1 BFS：边权只有 0 和 1 的最短路
- 模拟双端操作：如某些卡牌游戏、排队问题
✨ 常见错误
- 对空 deque 调用 front/back：未检查 empty() 就访问，导致未定义行为
- 混淆 deque 和 queue：queue 只支持尾入头出，deque 两端都可以
- 竞赛中误用 deque 替代 vector：deque 的随机访问虽然是 O(1)，但常数较大，不如 vector 快
- 滑动窗口中下标管理错误：deque 中存的是下标还是值要分清楚
- 0-1 BFS 中忘记判断是否已经更新：导致元素重复入队，效率下降
✨ 算法评价
| 应用场景 | 时间复杂度 | 说明 |
|---|---|---|
| 基本双端操作 | O(1) 每次 | push/pop front/back |
| 滑动窗口最值 | O(n) | 配合单调队列 |
| 0-1 BFS | O(V + E) | 替代 Dijkstra |
| 随机访问 | O(1) | 但常数比 vector 大 |
deque 是一个功能强大的数据结构，掌握它是学习单调队列和 0-1 BFS 的基础。竞赛中最常见的用法是作为单调队列的底层容器。