vector 和 list 的"混血儿"——既能下标随机访问，又能在两端 O(1) 增删，序列容器系列的最后一站。
deque 是 C++ 标准库中的双端队列，全称 Double-Ended Queue。是 vector 和 list 的"混血儿"：它既支持下标随机访问，又支持在头部和尾部快速增删。底层由多段连续空间拼接而成，所以头部操作也是 O(1)。使用前需引入 <deque> 头文件。
deque 支持 O(1) 的头部和尾部插入/删除，弥补了 vector 头部操作慢的缺点。deque 支持 operator[] 和 at() 随机访问，弥补了 list 不能随机访问的缺点。deque 的底层是分段连续空间，不是一整块连续内存，因此某些需要连续内存指针的场景（如传给 C 风格接口）不适合用 deque。
| 1 | #include <iostream> |
| 2 | #include <deque> // 必须包含这个头文件 |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | deque<int> dq1; // 空双端队列 |
| 8 | deque<int> dq2(5); // 5 个元素，全部初始化为 0 |
| 9 | deque<int> dq3(5, 7); // 5 个元素，全部初始化为 7 |
| 10 | deque<int> dq4 = {1, 2, 3, 4, 5}; // 初始化列表 |
| 11 | deque<int> dq5(dq4); // 拷贝构造 |
| 12 | return 0; |
| 13 | } |
deque 拥有 vector 的全部功能（[]、at()、size()、empty() 等），同时额外支持头部操作：
| 1 | deque<int> dq = {2, 3, 4}; |
| 2 | // 头部操作（vector 没有的！） |
| 3 | dq.push_front(1); // {1, 2, 3, 4} |
| 4 | dq.pop_front(); // {2, 3, 4} |
| 5 | // 尾部操作（和 vector 一样） |
| 6 | dq.push_back(5); // {2, 3, 4, 5} |
| 7 | dq.pop_back(); // {2, 3, 4} |
| 8 | // 随机访问（list 没有的！） |
| 9 | cout << dq[1] << endl; // 输出：3——支持下标访问 |
| 10 | cout << dq.at(0) << endl; // 输出：2——支持 at 访问 |
deque 底层是分段连续空间，不是一整块连续内存，所以没有 data() 函数。如果需要把数据传给要求连续内存的 C 函数，不能用 deque，请用 vector。
| 1 | #include <iostream> |
| 2 | #include <deque> |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | deque<int> dq; |
| 8 | |
| 9 | // 头部和尾部都能插入 |
| 10 | dq.push_back(2); // {2} |
| 11 | dq.push_front(1); // {1, 2} |
| 12 | dq.push_back(3); // {1, 2, 3} |
| 13 | dq.push_front(0); // {0, 1, 2, 3} |
| 14 | |
| 15 | // 随机访问 |
| 16 | cout << "第2个元素: " << dq[1] << endl; // 输出：1 |
| 17 | cout << "首元素: " << dq.front() << endl; // 输出：0 |
| 18 | cout << "尾元素: " << dq.back() << endl; // 输出：3 |
| 19 | |
| 20 | // 遍历 |
| 21 | cout << "遍历: "; |
| 22 | for (int x : dq) { |
| 23 | cout << x << " "; // 输出：0 1 2 3 |
| 24 | } |
| 25 | cout << endl; |
| 26 | |
| 27 | // 头部和尾部删除 |
| 28 | dq.pop_front(); // {1, 2, 3} |
| 29 | dq.pop_back(); // {1, 2} |
| 30 | |
| 31 | cout << "大小: " << dq.size() << endl; // 输出：2 |
| 32 | |
| 33 | return 0; |
| 34 | } |
| 容器 | 随机访问 | 头部增删 | 尾部增删 | 中间增删 | 典型场景 |
|---|---|---|---|---|---|
| vector | O(1) | O(n) | O(1) | O(n) | 大多数场景的默认选择 |
| list | 不支持 | O(1) | O(1) | O(1) | 频繁在中间插入/删除 |
| deque | O(1) | O(1) | O(1) | O(n) | 两端都要快速操作（如滑动窗口） |
| string | O(1) | O(n) | O(1) | O(n) | 文本处理（本质是特化的 vector<char>） |
把本节出现过的方法按用途归类汇总，写代码时可以直接当参考卡用。
| 方法 | 分类 | 作用 |
|---|---|---|
| dq.size() / dq.empty() | 容量 | 元素个数 / 判断是否为空 |
| dq.clear() | 容量 | 清空所有元素 |
| dq[i] | 访问 | 下标访问，不检查越界 |
| dq.at(i) | 访问 | 下标访问，越界抛异常 |
| dq.front() / dq.back() | 访问 | 第一个 / 最后一个元素 |
| dq.push_front(x) / dq.pop_front() | 修改 | 头部插入 / 删除，O(1)（vector 没有） |
| dq.push_back(x) / dq.pop_back() | 修改 | 尾部插入 / 删除，O(1) |
| dq.insert(it, x) / dq.erase(it) | 修改 | 中间插入 / 删除，O(n) |
| dq1.swap(dq2) | 修改 | 交换两个 deque 的全部内容 |
| dq.begin() / dq.end() | 遍历 | 正向迭代器范围 |
queue / stack（下一节）更直接。