双端队列(Deque)

定义

双端队列(Double-Ended Queue,简称 Deque)是一种允许在头部和尾部两端进行插入与删除的线性数据结构,是栈和队列的泛化形式。

实现

常见实现有三种:环形数组(如 C++ 早期实现思路)、分块数组(如 C++ STL 的 std::deque,由多个固定大小的块加索引表组成)以及双向链表。分块数组实现兼顾了随机访问与两端 O(1) 扩展。Python 的 collections.deque 则基于双向块链表。

应用

双端队列是滑动窗口最值(单调队列)算法的基础容器;工作窃取(work stealing)调度器中,每个线程用双端队列存放任务,自己从一端取、其他线程从另一端偷;此外也可直接当栈或队列使用。

优缺点

优点是两端操作均为 O(1)、用途灵活;缺点是分块实现的中间插入删除代价高,内存布局也比纯数组复杂。