C++ deque怎么用？双端队列使用教程【STL】

std::deque是C++中支持头尾高效插入删除且具备随机访问能力的双端队列容器，底层采用分段连续内存实现；它兼顾vector的O(1)随机访问与list的部分O(1)首尾操作优势，适用于需频繁两端操作又偶有索引访问的场景。

std::deque（double-ended queue）是C++标准库中一种支持在头尾高效插入和删除的序列容器，底层通常以分段连续空间实现，兼顾了vector的随机访问能力和list的部分插入效率。它不是“队列”而是“双端队列”，比queue更灵活，适合需要频繁在两端操作、又偶尔按索引访问的场景。

基本用法：声明、初始化与常用操作

包含头文件 #include 即可使用。

• 声明空deque：std::deque dq;
• 带初始元素：std::deque dq = {1, 2, 3}; 或 std::deque dq(5, 0);（5个0）
• 尾部插入/删除：dq.push_back(4); dq.pop_back();
• 头部插入/删除：dq.push_front(0); dq.pop_front();
• 随机访问：dq[2] 或 dq.at(2)（后者带越界检查）

与vector、list的关键区别在哪？

理解差异才能选对容器：

• 内存布局：deque是“分段连续”，每段固定大小的缓冲区；vector是单一连续内存；list是双向链表
• 随机访问：deque和vector都是O(1)，list是O(n)
• 首尾插入/删除：deque稳定O(1)；vector在尾部O(1)，头部O(n)；list全O(1)
• 迭代器失效规则：deque只有在首/尾插入导致扩容时，才可能使所有迭代器失效（不像vector只影响尾后）；删除元素不导致其他位置迭代器失效

实用技巧与注意事项

实际写代码时容易踩坑，注意这些点：

• 不要假设deque内存连续——&dq[0]不能安全转成原生指针数组传给C接口（vector可以）
• 清空用dq.clear()，但不保证释放内存；如需彻底释放，可交换空deque：std::deque().swap(dq);
• 遍历时优先用范围for或迭代器，避免反复调用size()（虽然O(1)，但语义不如empty()清晰）
• 若只需单向队列行为（FIFO），直接用std::queue（默认基于deque）更语义明确

一个小例子：滑动窗口最大值（体现deque优势）

经典问题中，deque常用来维护单调队列：

// 维护窗口内从大到小的下标（值递减）
std::deque dq; // 存储nums中的索引
for (int i = 0; i < nums.size(); ++i) {
    // 移除超出窗口的索引
    if (!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()]);
}

这里利用deque头尾均可O(1)操作的特性，高效维护窗口信息。

基本上就这些。deque不是万能，但当你需要“既能快速取首尾、又能按位置查元素”时，它往往是比vector+erase(0)或list+advance更优的选择。