双端队列 | Codeboy's Blog

形式陈述

双端队列（deque）是一种抽象数据类型，其状态是有限序列 $D=(x_0,\ldots,x_{n-1})$ 。它支持

\begin{aligned} \operatorname{push\_front}(x)&:(x_0,\ldots)\mapsto(x,x_0,\ldots),\\ \operatorname{push\_back}(x)&:(\ldots,x_{n-1})\mapsto(\ldots,x_{n-1},x),\\ \operatorname{pop\_front}()&:(x_0,x_1,\ldots)\mapsto(x_0,(x_1,\ldots)),\\ \operatorname{pop\_back}()&:(\ldots,x_{n-2},x_{n-1})\mapsto(x_{n-1},(\ldots,x_{n-2})). \end{aligned}

空队列上的弹出必须由接口规定为错误、空结果或禁止调用。只使用 push_back 与 pop_front 时，它退化为 FIFO 队列；只在同一端压入和弹出时，它表现为栈。

循环数组实现维护正容量 $C$ 、长度 $n$ 和首元素下标 $h$ ，逻辑位置 $i$ 存在物理槽 $(h+i)\bmod C$ 。若用动态数组管理容量，满时按逻辑次序复制到几何增长的新区块，删除时不缩容或采用有滞回的缩容阈值，则四个端点更新均为摊还 $O(1)$ ；不发生扩缩容的调用为最坏 $O(1)$ 。双向链表保存首尾指针，在节点分配、释放及局部指针操作都按常数成本计算时，也给出最坏 $O(1)$ 端点操作，但不承诺常数时间随机访问。

直觉

普通队列把进入端和离开端固定下来，deque 则允许算法根据局部结构选择把候选放到哪一端、从哪一端取走。序列次序仍是唯一的；灵活性来自两端都是合法更新位置，而不是取消顺序。循环数组通过让下标在存储区末端回绕，复用前端弹出后留下的空间，避免每次移动所有剩余元素。

存储是否连续、迭代器是否稳定以及能否按下标访问，取决于具体实现。需要这些能力时，应查阅所选容器的接口保证。

例子与边界

从空 deque 执行 push_back(a)、push_back(b)、push_front(c) 后，序列是 $(c,a,b)$ ；随后 pop_back() 返回 $b$ ，而 pop_front() 返回 $c$ 。这组操作同时用到两端，无法用一个只暴露队头删除、队尾插入的 FIFO 接口原样表达。

0–1 BFS 处理边权为 $0$ 或 $1$ 的图。一次松弛严格降低顶点距离时，把“入队时的距离、顶点”作为一项保存：权为 $0$ 时放到前端，权为 $1$ 时放到后端。取出时，若保存的距离已不同于该顶点的当前距离，就跳过这份旧项；实际扩展的有效项按距离非降序出现。只存顶点编号时，同一顶点的旧副本仍可能留在队列中，因此不能把整列编号的当前距离都当作已排序。滑动窗口最值则从尾部删除已不可能成为答案的元素，并从头部移除过期下标。两者都依赖端点操作，但分别需要最短路的有效项次序和窗口的单调性不变量。

0–1 BFS独立算法页保留本段的快照约定，补出两个相邻距离层的不变量、每点至多两次入队及路径重建。它也给出第一次发现不能锁定距离的反例；这些结论是该零一权工作负载的性质，不是deque本身自动提供的优先队列保证。

数组实现发生扩容时，单次操作需要复制 $\Theta(n)$ 个元素，所以“常数时间”只能是摊还保证；有严格尾延迟要求时必须另选固定容量或分块实现。链表虽可最坏常数更新端点，却付出指针空间和较差局部性。

推论与应用

Deque 统一覆盖 FIFO 与 LIFO 的端点行为，常用于工作窃取调度、回文扫描、0–1 BFS 和单调队列。选择实现时，应把算法实际需要的保证逐项对照：循环数组适合局部性与随机访问扩展，链式或分块结构适合稳定地址与避免整块搬迁；任何额外性质都应写在实现契约中。

Deque 直接取出的是首端或尾端元素。若算法能维持“所需候选始终位于端点”的不变量，例如 0–1 BFS 跳过旧项后取出距离最小的有效项，就能用端点操作完成选择；任意优先级的候选通常需要优先队列来维护最小者。

参考资料

Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, §10.1, stacks and queues.
Kurt Mehlhorn and Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer, 2008, Ch. 3, sequences and queue implementations.

形式陈述 ​

反向链接

形式陈述