双端队列

形式陈述 ​

双端队列（deque）是一种抽象数据类型公理库抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。，其状态是有限序列 $D=(x_0,\dots ,x_{n-1})$。它支持

$$\begin{array}{rl}\mathrm{push}\mathrm{\_}\mathrm{front}(x)& :(x_0,\dots )\mapsto (x,x_0,\dots ),\\ \mathrm{push}\mathrm{\_}\mathrm{back}(x)& :(\dots ,x_{n-1})\mapsto (\dots ,x_{n-1},x),\\ \mathrm{pop}\mathrm{\_}\mathrm{front}()& :(x_0,x_1,\dots )\mapsto (x_0,(x_1,\dots )),\\ \mathrm{pop}\mathrm{\_}\mathrm{back}()& :(\dots ,x_{n-2},x_{n-1})\mapsto (x_{n-1},(\dots ,x_{n-2})).\end{array}$$

空队列上的弹出必须由接口规定为错误、空结果或禁止调用。只使用 push_back 与 pop_front 时，它退化为 FIFO 队列公理库队列Queue · FIFO queue在尾部插入、头部删除、遵循先进先出的结构。；只在同一端压入和弹出时，它表现为栈。双端能力描述的是一条序列的两个端点，不是把两个互不相干的队列拼在一起。

循环数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。实现维护容量 $C$、长度 $n$ 和首元素下标 $h$，逻辑位置 $i$ 存在物理槽 $(h+i)modC$。不扩容时四个端点操作均为最坏 $O(1)$；采用几何扩容后为摊还 $O(1)$。双向链表公理库链表Linked list节点通过指针连接并支持局部插入删除的线性数据结构。在保存首尾指针时也给出最坏 $O(1)$ 端点操作，但不承诺常数时间随机访问。

直觉 ​

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

抽象接口不决定容器是否连续、迭代器会不会失效，也不保证中间插删或按下标访问。把某种语言标准库的 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$ 的松弛放到后端，使待处理顶点保持按当前距离分层；滑动窗口最值则从尾部删除已不可能成为答案的元素，并从头部移除过期下标。两者都依赖端点操作，但维护的不变量不同，deque 本身不会自动产生最短路或单调性。

数组实现发生扩容时，单次操作需要复制 $\mathrm{\Theta }(n)$ 个元素，所以“常数时间”只能是摊还保证；有严格尾延迟要求时必须另选固定容量或分块实现。链表虽可最坏常数更新端点，却付出指针空间和较差局部性。随机访问、按优先级取最小元素以及删除任意中间位置都不是 deque 的必备能力。

推论与应用 ​

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

与优先队列的差别尤其重要：deque 只能取当前首或尾，不能根据任意键选出全局最优元素。若算法正确性依赖“每次取最小距离”，需要的是优先队列；若只需在两种已知优先级之间把新元素放到不同端点，deque 才足够。

参考资料

• 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.