deque是C++ STL中支持首尾O(1)插入删除及O(1)随机访问的双端队列，底层基于分段连续缓冲区，首尾操作不使迭代器失效，适合滑动窗口、撤销栈等两端频繁操作场景。
deque（double-ended queue，双端队列）是 C++ STL 中的一种序列容器，支持在**头部和尾部高效地插入与删除元素**，同时也能像 vector 一样支持随机访问（通过下标 [] 或 at()）。它底层通常由**分段连续的缓冲区数组**实现（非单一连续内存），兼顾了 vector 的快速随机访问和 list 的首尾操作效率。
deque 的核心特点
• 支持 O(1) 时间复杂度的 push_front()、pop_front()、push_back()、pop_back()
• 支持 O(1) 随机访问（operator[]、at()、front()、back()）
• 迭代器支持双向移动（++、--），但**不保证迭代器失效规则像 vector 那样简单**：首尾操作不会使其他迭代器/引用/指针失效（这是 deque 的关键优势）
• 中间插入/删除（如 insert()、erase() 非首尾位置）是 O(n)，应避免频繁使用
• 内存占用略高于 vector（需维护缓冲区管理结构），缓存局部性稍差（因数据不完全连续）
deque 的典型使用场景
• 需要频繁在两端增删的队列类结构：比如滑动窗口最大值、任务调度中的双端优先队列、撤销/重做栈（一端进，另一端出）
• 作为动态大小的“可伸缩数组”，且不能接受 vector 在扩容时迭代器批量失效：例如多线程中某线程持有 deque 中间元素的迭代器，而另一线程在首尾操作——deque 能保证该迭代器仍有效
• 替代 vector 处理大量首部插入需求：vector 的 insert(begin(), x) 是 O(n)，deque 的 push_front(x) 是 O(1)
• 实现某些算法的数据结构基础：如广度优先搜索（BFS）中用 deque 做队列（虽然 queue 适配器更常见），或实现“单调队列”优化 DP
deque 的常用方法速查
• 构造与赋值：deque、deque（5 个 10）、d.assign(3, 7);
• 元素访问：d[2]、d.at(2)（带越界检查）、d.front()、d.back()
• 插入删除：d.push_back(x)、d.pop_back()、d.push_front(x)、d.pop_front()
• 迭代器：d.begin()、d.end()、d.rbegin()、d.rend()
• 容量操作：d.size()、d.empty()、d.clear()、d.resize(n)
• 扩展操作：d.insert(it, x)（O(n)，慎用）、d.erase(it) 或 d.erase(first, last)
deque 和其他容器的对比提醒
• vs vector：vector 更省内存、缓存友好、适合尾部操作+随机访问；deque 胜在首部操作稳定高效，且首尾操作不导致迭代器失效
• vs list：list 支持任意位置 O(1) 插删，但不支持随机访问，且每个节点有额外指针开销；deque 折中——只优化首尾，换来了下标访问能力
• vs queue / stack：它们是容器适配器，默认底层就是 deque（也可指定为 list）；直接用 deque 更灵活，能自由访问中间、遍历、反转等
