双端队列Deque

允许在两端插入和移除元素的序列接口。

核心约束: 两端操作都保持内部元素的相对顺序。
适用问题: 工作窃取、窗口候选维护与双端任务缓冲。
边界与取舍: 随机访问与中间删除成本取决于环形数组或链表等实现。

常见操作#

n 为双端队列元素数。

操作	时间复杂度	条件与说明
查看首尾元素	$O(1)$	保存首尾指针或首尾下标。
两端插入 / 删除	摊还 $O(1)$	以 ArrayDeque 为例；扩容的一次插入最坏 $O(n)$ 。双向链表链接修改为 $O(1)$ 。
按值查找 / 删除中间元素	$O(n)$	需要定位目标；数组实现还需移动部分元素。
遍历	$O(n)$	顺序访问 n 个元素。

时间与空间#

时间复杂度: 两端操作常数或摊还常数时间
存储空间: $O(n)$

双端队列是接口语义，不能把数组的随机访问保证推广到所有 deque 实现。

工程中的应用#

2 个案例 · 附源码

Redis·List 数据类型 / quicklist 编码7.2.0

用分块双端结构保存 Redis List

Redis List 提供左右两端的插入和弹出；在 quicklist 编码下，用带头尾指针的双向节点链组织紧凑数据块。

双端队列链表

附源码片段 · 内存管理

vLLM·V1 推理调度器v0.8.5

在 token 预算和 KV 容量内连续安排请求

vLLM V1 每轮分配 token 预算，先继续运行中的请求，再尝试接纳等待者；KV 块不足时抢占请求，把它放回等待队列。

连续批处理分块与页映射双端队列

附源码片段 · 调度与资源分配

基础原理参考资料

Java 21 · ArrayDeque两端操作的摊还常数成本，以及搜索和中间删除的线性例外。