Appearance
第4章 deque 容器详解
deque（double-ended queue，双端队列）是 STL 中的序列式容器，底层采用分段连续内存（由多个固定大小的缓冲区组成），通过一个中控器（map）管理这些缓冲区，既支持随机访问，又支持高效的头尾插入删除，是 vector 和 list 的一种折中方案。
🎯 本章学习目标
学完本章，你将能够：
- 理解 deque 的"分段连续内存"底层结构
- 熟练使用 deque 的头尾插入删除操作
- 掌握 deque 的随机访问特性
- 理解 deque 中控器 + 缓冲区的实现原理
- 区分 deque 与 vector、list 的核心区别
- 掌握 deque 作为 stack 和 queue 默认底层容器的原因
- 根据场景选择 deque 还是 vector 还是 list
- 了解 deque 的常见误区与注意事项
🗺️ 本章知识图谱
deque 双端队列
├── 核心特性
│ ├── 分段连续内存
│ ├── 双端操作 O(1)
│ ├── 随机访问 O(1)
│ └── 中间插入 O(n)
├── 基本用法
│ ├── 定义与头文件
│ ├── 头尾插入（push_front、push_back）
│ ├── 头尾删除（pop_front、pop_back）
│ ├── 随机访问（[]、at）
│ ├── 中间插入删除（insert、erase）
│ └── 遍历方式
├── 底层原理
│ ├── 中控器（map）
│ ├── 缓冲区（buffer）
│ ├── 扩容机制
│ └── 迭代器实现
├── 与其他容器对比
│ ├── vs vector
│ ├── vs list
│ └── 作为 stack/queue 底层
├── 注意事项
│ ├── 内存不真正连续
│ ├── 迭代器较复杂
│ └── 中间插入效率低
└── 适用场景与选型一、deque 核心特性
🍎 生活比喻：deque 就像地铁——地铁有很多节车厢（缓冲区），每节车厢内部座位是连续的，但车厢和车厢之间是通过挂钩连接的（分段连续）。你可以从车头门上车（头插），也可以从车尾门上车（尾插），还可以直接走到第 N 节车厢的某个座位（随机访问）。如果人太多，就再加一节车厢（扩容不需要移动原有元素）。
- 分段连续内存：deque 不是一整块连续内存，而是由多个固定大小的缓冲区（buffer）组成，通过中控器管理，逻辑上看起来是连续的；
- 双端高效操作：头部和尾部插入删除都是 O(1)，比 vector 多了高效的头插/头删；
- 支持随机访问：通过
[]或at()可以 O(1) 时间访问任意位置的元素（但效率略低于 vector）； - 中间插入删除效率低：中间插入删除需要移动元素，时间复杂度 O(n)；
- 无 capacity 概念：deque 不需要预留空间，扩容时只需要新增缓冲区，不需要拷贝原有元素。
🔥 高频考点：deque 的双端 O(1) 操作、支持随机访问、分段连续内存，这些是选择题的常考点。
二、deque 基础用法（完整代码）
使用 deque 需包含 <deque> 头文件。
cpp
#include <iostream>
#include <deque> // deque的头文件
using namespace std;
int main() {
// 1. 定义deque（多种方式）
deque<int> d1; // 空deque
deque<int> d2(5, 0); // 5个元素，都初始化为0
deque<int> d3 = {1, 2, 3, 4, 5}; // 初始化列表（C++11）
// 2. 头尾插入（都是O(1)，这是deque的优势）
d1.push_back(10); // 尾插
d1.push_back(20);
d1.push_front(5); // 头插（vector没有这个高效操作！）
d1.push_front(1);
// 此时d1：[1, 5, 10, 20]
// 3. 随机访问（O(1)，支持下标和at）
cout << "d1[2] = " << d1[2] << endl; // 输出：10（无越界检查）
cout << "d1.at(1) = " << d1.at(1) << endl; // 输出：5（有越界检查）
// 4. 访问头尾元素
cout << "队头：" << d1.front() << endl; // 输出：1
cout << "队尾：" << d1.back() << endl; // 输出：20
// 5. 头尾删除（都是O(1)）
d1.pop_front(); // 删除队头，d1变为：[5, 10, 20]
d1.pop_back(); // 删除队尾，d1变为：[5, 10]
// 6. 中间插入（O(n)，效率较低）
d1.insert(d1.begin() + 1, 8); // 在索引1处插入8
// d1变为：[5, 8, 10]
// 7. 遍历（支持范围for）
cout << "遍历d1：";
for (int x : d1) {
cout << x << " ";
}
cout << endl; // 输出：5 8 10
// 8. 常用操作
cout << "大小：" << d1.size() << endl; // 输出：3
cout << "是否为空：" << (d1.empty() ? "是" : "否") << endl;
d1.clear(); // 清空所有元素
return 0;
}操作汇总表
| 操作 | 语法 | 说明 | 时间复杂度 |
|---|---|---|---|
| 头插 | push_front(元素) | 在头部插入元素 | O(1) |
| 尾插 | push_back(元素) | 在尾部插入元素 | O(1) |
| 头删 | pop_front() | 删除头部元素 | O(1) |
| 尾删 | pop_back() | 删除尾部元素 | O(1) |
| 访问头 | front() | 返回头部元素引用 | O(1) |
| 访问尾 | back() | 返回尾部元素引用 | O(1) |
| 随机访问 | [] / at() | 访问指定位置元素 | O(1) |
| 中间插入 | insert(迭代器, 元素) | 在指定位置插入 | O(n) |
| 中间删除 | erase(迭代器) | 删除指定位置元素 | O(n) |
| 清空 | clear() | 删除所有元素 | O(n) |
| 判空 | empty() | 是否为空 | O(1) |
| 大小 | size() | 返回元素个数 | O(1) |
💡 小技巧：如果你需要频繁在两端操作，又需要随机访问，deque 是最佳选择。vector 只擅长尾插，list 不支持随机访问，deque 正好兼顾了两者。
三、底层原理（进阶）
deque 的底层设计非常巧妙，它由两部分组成：中控器（map） 和 缓冲区（buffer）。
1. 中控器（map）
中控器是一个指针数组（名字叫 map，但不是 STL 的 map 容器），每个元素指向一个缓冲区的起始地址。中控器负责管理所有的缓冲区。
2. 缓冲区（buffer）
每个缓冲区是一块连续的固定大小的内存，用来存储实际的元素。缓冲区的大小由编译器决定（通常是 512 字节或元素大小的若干倍）。
3. 工作原理
- 元素分散存储在各个缓冲区中；
- 中控器记录每个缓冲区的地址；
- 当头部需要插入元素且第一个缓冲区已满时，在中控器前面新增一个缓冲区；
- 当尾部需要插入元素且最后一个缓冲区已满时，在中控器后面新增一个缓冲区；
- 随机访问时，先通过索引计算出在第几个缓冲区的第几个位置，再直接访问。
🍎 生活比喻：中控器就像酒店的前台索引牌，上面写着每层楼（缓冲区）的房间号范围。你要找 208 号房间，先看索引牌知道在 2 楼，然后去 2 楼找 08 号房间。
4. 扩容机制
deque 的扩容比 vector 高效得多：
- vector 扩容需要分配新内存 + 拷贝所有元素 + 释放旧内存（O(n)）；
- deque 扩容只需要新增一个缓冲区 + 更新中控器（O(1)）；
- 原有元素不需要移动，迭代器也不会全部失效。
⚠️ 易错点：deque 扩容时原有元素的内存地址不会改变，但迭代器可能会失效（因为中控器可能扩容了）。不过引用和指向元素的指针仍然有效。
四、deque 与其他容器对比
| 特性 | vector | deque | list |
|---|---|---|---|
| 内存结构 | 一整块连续 | 分段连续 | 不连续（链表） |
| 随机访问 | ✅ O(1)（最快） | ✅ O(1)（稍慢） | ❌ O(n) |
| 尾插尾删 | ✅ O(1)（均摊） | ✅ O(1) | ✅ O(1) |
| 头插头删 | ❌ O(n) | ✅ O(1) | ✅ O(1) |
| 中间插入删除 | ❌ O(n) | ❌ O(n) | ✅ O(1) |
| 迭代器类型 | 随机访问迭代器 | 随机访问迭代器 | 双向迭代器 |
| 空间开销 | 小（连续内存） | 中（中控器+缓冲区） | 大（每个节点有指针） |
| 缓存友好性 | 最好（连续内存） | 一般（分段连续） | 差（内存分散） |
🔥 高频考点：vector、deque、list 三者的对比是选择题和简答题的高频考点，必须熟记。
五、为什么 stack 和 queue 默认用 deque 作底层？
这是一个经典的面试题/考试题，原因有三：
- 双端操作都高效：stack 只需要栈顶操作，queue 需要头尾操作，deque 的头尾操作都是 O(1)，完美满足需求；
- 扩容不需要拷贝元素：vector 扩容时需要拷贝所有元素，性能开销大。deque 扩容只需要新增缓冲区，不会移动原有元素；
- 容量浪费少：vector 会预留多余空间（capacity > size），造成一定浪费。deque 的空间利用率更高，不用的缓冲区可以释放。
所以 deque 作为 stack 和 queue 的默认底层容器，是性能和功能的最佳平衡点。
六、常见误区与注意事项
⚠️ 易错点 1：认为 deque 内存是完全连续的。deque 是分段连续的，不同缓冲区之间的地址不连续。不能像 vector 那样用指针运算来遍历。
⚠️ 易错点 2：认为 deque 的随机访问和 vector 一样快。deque 的随机访问需要先计算在哪个缓冲区，多了一次寻址，比 vector 稍慢。但时间复杂度都是 O(1)。
⚠️ 易错点 3：中间插入删除效率高。deque 只在头尾高效，中间插入删除仍然是 O(n)，因为需要移动元素。如果需要频繁中间插入，应该用 list。
⚠️ 易错点 4：deque 有 capacity() 和 reserve()。deque 没有容量概念，也没有 reserve() 函数，因为它不需要预留连续空间。
⚠️ 易错点 5：迭代器一定不失效。deque 在头尾插入时，指向元素的引用和指针仍然有效，但迭代器可能会失效（因为中控器可能重新分配了）。
七、适用场景总结
- 需要双端高效操作：同时需要在头部和尾部频繁插入删除的场景（如滑动窗口、双端队列）；
- 作为适配器底层：作为 stack 和 queue 的默认底层容器（已经替你选好了）；
- 需要随机访问 + 头插：既要随机访问，又要高效头插，这是 deque 独有的优势；
- 数据量不确定且增长方向不确定：不知道数据会从哪边增长时，deque 比 vector 更灵活。
不适合的场景：
- 极致性能的随机访问 → 用 vector
- 频繁中间插入删除 → 用 list
- 需要连续内存传给 C 接口 → 用 vector
八、🔖 本章小结
deque 是一种折中设计的序列式容器，用分段连续内存的方式，同时实现了高效的双端操作和随机访问。它是 vector 和 list 之间的平衡点：比 vector 多了高效头插，比 list 多了随机访问。默认作为 stack 和 queue 的底层容器，日常开发中如果不确定用 vector 还是 list，deque 往往是一个不错的选择。
九、📝 实战练习
练习题 1（选择题）
题目： deque 的底层存储结构是？
A. 一整块连续内存 B. 分段连续内存（多个缓冲区） C. 双向链表 D. 红黑树
🔑 点击查看答案与解析
答案： B
**解析：**deque 底层是分段连续内存，由多个固定大小的缓冲区组成，通过中控器管理。A 是 vector 的底层结构，C 是 list 的底层结构，D 是 set/map 的底层结构。
练习题 2（选择题）
题目： 以下哪种操作，deque 的时间复杂度不是 O(1)？
A. push_front B. push_back C. 随机访问 [] D. 中间位置 insert
🔑 点击查看答案与解析
答案： D
**解析：**deque 的头插、尾插、随机访问都是 O(1)。但中间插入（insert）需要移动元素，时间复杂度是 O(n)。这是 deque 的短板，和 vector 一样。
练习题 3（判断题）
题目： deque 有 capacity() 方法，可以查看当前容量（ ）
🔑 点击查看答案与解析
答案： 错误
**解析：**deque 没有 capacity() 和 reserve() 方法。因为 deque 是分段连续内存，不需要像 vector 那样预留一整块连续空间，也就没有"容量"的概念。deque 的空间是按需分配缓冲区的。
练习题 4（选择题）
题目： stack 和 queue 默认使用 deque 作为底层容器，以下哪个不是原因？
A. deque 的头尾操作都是 O(1) B. deque 扩容时不需要拷贝原有元素 C. deque 的随机访问比 vector 快 D. deque 的空间利用率更高
🔑 点击查看答案与解析
答案： C
解析：
- A 是原因：deque 头尾 O(1) 正好满足 stack 和 queue 的需求
- B 是原因：deque 扩容只新增缓冲区，不需要拷贝
- C 不是原因：deque 的随机访问比 vector 慢（需要计算缓冲区位置），而且 stack/queue 也不需要随机访问
- D 是原因：deque 没有 capacity > size 的空间浪费
练习题 5（程序阅读题）
题目： 阅读以下代码，写出输出结果：
cpp
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d;
d.push_back(3);
d.push_front(2);
d.push_back(4);
d.push_front(1);
cout << d[2] << " " << d.front() << " " << d.back() << endl;
d.pop_front();
d.pop_back();
cout << d.size() << endl;
return 0;
}🔑 点击查看答案与解析
答案：
3 1 4
2解析：
- push_back(3) → [3]
- push_front(2) → [2, 3]
- push_back(4) → [2, 3, 4]
- push_front(1) → [1, 2, 3, 4]
- d[2] = 3，d.front() = 1，d.back() = 4 → 输出：3 1 4
- pop_front() → [2, 3, 4]
- pop_back() → [2, 3]
- d.size() = 2 → 输出：2
最终输出：
3 1 4
2练习题 6（选择题）
题目： 关于 vector、deque、list 的对比，以下说法正确的是？
A. 三者都支持随机访问 B. 三者的尾插都是 O(1) C. 只有 list 支持头插 O(1) D. 三者的中间插入都是 O(n)
🔑 点击查看答案与解析
答案： B
解析：
- A 错误：list 不支持随机访问
- B 正确：vector（均摊）、deque、list 的尾插都是 O(1)
- C 错误：deque 和 list 的头插都是 O(1)，vector 是 O(n)
- D 错误：list 的中间插入是 O(1)（只要有迭代器）
练习题 7（编程题）
题目： 使用 deque 实现一个滑动窗口的最大值问题。给定一个数组和窗口大小 k，求每个窗口中的最大值。（简化版：只需要输出所有窗口的最大值之和）
**输入格式：**第一行两个整数 n 和 k，第二行 n 个整数 **输出格式：**一个整数，表示所有窗口最大值的和
样例输入：
8 3
1 3 -1 -3 5 3 6 7样例输出：
28解释：窗口分别为 [1,3,-1]、[3,-1,-3]、[-1,-3,5]、[-3,5,3]、[5,3,6]、[3,6,7]，最大值分别为 3、3、5、5、6、7，和为 3+3+5+5+6+7=28。
🔑 点击查看答案与解析
参考代码：
cpp
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
deque<int> dq; // 存储下标，保持对应的值单调递减
long long sum = 0;
for (int i = 0; i < n; i++) {
// 移除队尾比当前元素小的（它们不可能成为后面窗口的最大值）
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
// 移除超出窗口范围的队头
while (dq.front() <= i - k) {
dq.pop_front();
}
// 窗口形成后，队头就是最大值
if (i >= k - 1) {
sum += nums[dq.front()];
}
}
cout << sum << endl;
return 0;
}**解析：**这是经典的"滑动窗口最大值"问题，最优解法就是用 deque 实现单调队列。核心思路：
- deque 中存储元素的下标，且对应的值保持单调递减
- 新元素入队前，先把队尾比它小的都弹出（因为它们不可能成为后面窗口的最大值）
- 队头元素如果超出窗口范围，就从队头弹出
- 每次窗口形成时，队头就是当前窗口的最大值
这道题是 deque 最经典的应用之一，时间复杂度 O(n)。
十、📊 考点总结表
| 知识点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 分段连续内存结构 | ⭐⭐⭐⭐ | 选择题、判断题 | 以为是完全连续的 |
| 双端操作 O(1) | ⭐⭐⭐⭐⭐ | 选择题 | 与 vector 混淆 |
| 支持随机访问 | ⭐⭐⭐⭐ | 选择题 | 与 list 混淆 |
| 中间插入 O(n) | ⭐⭐⭐ | 选择题 | 以为中间插入也是 O(1) |
| 无 capacity/reserve | ⭐⭐⭐ | 判断题 | 以为和 vector 一样有容量 |
| 作为 stack/queue 默认底层 | ⭐⭐⭐⭐ | 选择题、简答题 | 不知道为什么用 deque |
| 与 vector/list 对比 | ⭐⭐⭐⭐⭐ | 选择题、简答题 | 三者区别记不清 |
| 单调队列（滑动窗口） | ⭐⭐⭐ | 编程题 | 维护单调性的逻辑 |
⭐ 必背速记卡
┌──────────────────────────────────────┐
│ deque 必背速记卡 │
├──────────────────────────────────────┤
│ 1. 双端队列，分段连续内存 │
│ 2. 头插头删、尾插尾删都是 O(1) │
│ 3. 支持随机访问 []，但比 vector 稍慢 │
│ 4. 中间插入删除 O(n)，需要移动元素 │
│ 5. 中控器 + 缓冲区，扩容只需新增buffer│
│ 6. 没有 capacity() 和 reserve() │
│ 7. 是 stack 和 queue 的默认底层容器 │
│ 8. 比 vector 多了头插，比list多了随机访问│
│ 9. 经典应用：滑动窗口、单调队列 │
│ 10. 折中设计，兼顾效率与功能 │
└──────────────────────────────────────┘