数据结构篇（七）：线性表——双端队列

前言前面讲了栈一端进出和队列一端进、一端出。这一篇讲双端队列——顾名思义它把栈和队列的能力结合在了一起两端都能插入两端都能删除。理解了双端队列再看C STL的deque、Java的ArrayDeque会更加清晰同时它也是很多算法题如滑动窗口最大值的核心数据结构。一、什么是双端队列双端队列Double-Ended Queue简称Deque是一种允许在两端都进行插入和删除操作的线性表。它的两端分别叫队头front和队尾rear/back支持四种基本操作队头入队push front队头出队pop front队尾入队push back队尾出队pop back可以看出双端队列其实是栈和队列的超集只用队尾两个操作push back pop back它就是一个栈只用队头出、队尾进push back pop front它就是一个队列。正因为如此双端队列的灵活性远高于栈和队列代价是实现相对更复杂一些。二、双端队列的实现方式和顺序表/链表的选择类似双端队列也有两种实现思路循环数组环形缓冲区实现用一个固定或可扩容的数组通过front和rear两个下标配合取模运算让数组首尾相连从而支持两端O(1)操作。这是STLdeque底层思路的简化版也是本文重点讲解的实现方式双向链表实现直接复用双向链表的头插、头删、尾插、尾删接口即可天然实现双端队列因为双向链表本身就支持O(1)的两端操作实现简单但相比数组实现多了指针开销和缓存局部性的劣势。本文以循环数组方式实现这也是最能体现双端队列设计精髓的方式。三、双端队列的结构定义循环数组实现的核心思路数组容量固定为capacity用front表示队头元素下标size表示当前有效元素个数通过(front i) % capacity计算逻辑第i个元素的实际存储位置实现数组的环形复用。​typedef int DQDataType; typedef struct Deque { DQDataType* array; int front; // 队头元素下标 int size; // 有效元素个数 int capacity; // 数组容量 } Deque;1.核心公式取模 % pdq-capacity只要下标计算带上% capacity下标超出数组末尾时就会绕回数组头部。 举个例子capacity 4数组下标 0、1、2、3下标 4 % 4 0 → 到数组开头下标 5 % 4 1下标 -1 % 4 3 → 向前走一步超出头部跳到数组末尾2.环形双端队列 所有下标计算公式// 1. 正向遍历/扩容拷贝取第i个逻辑元素 (i∈[0,size-1]) (pdq-front i) % pdq-capacity // 2. 尾插写入位置队尾下一个空位 (pdq-front pdq-size) % pdq-capacity // 3. 头插计算新队头下标防负数先加容量 (pdq-front - 1 pdq-capacity) % pdq-capacity // 4. 头删删除后新队头下标 (pdq-front 1) % pdq-capacity // 5. 获取队尾元素下标 (pdq-front pdq-size - 1) % pdq-capacity3.对应单行使用示例// 扩容拷贝 newArray[i] pdq-array[(pdq-front i) % pdq-capacity]; // 尾插 int backPos (pdq-front pdq-size) % pdq-capacity; // 头插更新front pdq-front (pdq-front - 1 pdq-capacity) % pdq-capacity; // 头删更新front pdq-front (pdq-front 1) % pdq-capacity; // 取队尾值 DQDataType backVal pdq-array[(pdq-front pdq-size - 1) % pdq-capacity];四、双端队列的基本操作4.1 初始化初始化函数外部传入 capacity核心原因让双端队列通用、灵活不写死存储空间大小void DequeInit(Deque* pdq, int capacity) { assert(pdq ! NULL); pdq-array (DQDataType*)malloc(capacity * sizeof(DQDataType)); if (pdq-array NULL) { perror(malloc fail); exit(-1); } pdq-front 0; pdq-size 0; pdq-capacity capacity; }4.2 检查容量扩容扩容时需要把原来环形排列的数据按逻辑顺序重新排列到新数组里不能直接realloc否则环形结构会被打乱。​void DequeCheckCapacity(Deque* pdq) { if (pdq-size pdq-capacity) { int newCapacity pdq-capacity * 2; DQDataType* newArray (DQDataType*)malloc(newCapacity * sizeof(DQDataType)); if (newArray NULL) { perror(malloc fail); exit(-1); } // 按逻辑顺序把旧数据拷贝到新数组 for (int i 0; i pdq-size; i) { newArray[i] pdq-array[(pdq-front i) % pdq-capacity]; } free(pdq-array); pdq-array newArray; pdq-front 0; // 重新排列后队头回到下标0 pdq-capacity newCapacity; } }4.3 队尾入队Push Back​void DequePushBack(Deque* pdq, DQDataType x) { assert(pdq ! NULL); DequeCheckCapacity(pdq); int rearIndex (pdq-front pdq-size) % pdq-capacity; pdq-array[rearIndex] x; pdq-size; }4.4 队头入队Push Front​void DequePushFront(Deque* pdq, DQDataType x) { assert(pdq ! NULL); DequeCheckCapacity(pdq); // front往前移一位利用取模实现绕回数组末尾 pdq-front (pdq-front - 1 pdq-capacity) % pdq-capacity; pdq-array[pdq-front] x; pdq-size; }4.5 队头出队Pop Front​void DequePopFront(Deque* pdq) { assert(pdq ! NULL); assert(pdq-size 0); pdq-front (pdq-front 1) % pdq-capacity; pdq-size--; }4.6 队尾出队Pop Backvoid DequePopBack(Deque* pdq) { assert(pdq ! NULL); assert(pdq-size 0); pdq-size--; // 队尾出队只需要减少size不涉及front变化 }4.7 取队头 / 队尾元素​DQDataType DequeFront(Deque* pdq) { assert(pdq ! NULL); assert(pdq-size 0); return pdq-array[pdq-front]; } DQDataType DequeBack(Deque* pdq) { assert(pdq ! NULL); assert(pdq-size 0); int rearIndex (pdq-front pdq-size - 1) % pdq-capacity; return pdq-array[rearIndex]; }4.8 判空bool DequeEmpty(Deque* pdq) { assert(pdq ! NULL); return pdq-size 0; }4.9 获取有效元素个数int DequeSize(Deque* pdq) { assert(pdq ! NULL); return pdq-size; }4.10 销毁void DequeDestroy(Deque* pdq) { assert(pdq ! NULL); free(pdq-array); pdq-array NULL; pdq-front pdq-size pdq-capacity 0; }五、完整测试代码int main() { Deque dq; DequeInit(dq, 4); DequePushBack(dq, 2); DequePushBack(dq, 3); DequePushFront(dq, 1); DequePushFront(dq, 0); // 逻辑顺序: 0 1 2 3 printf(队头: %d, 队尾: %d\n, DequeFront(dq), DequeBack(dq)); // 队头: 0, 队尾: 3 DequePopFront(dq); // 弹出0 DequePopBack(dq); // 弹出3 printf(队头: %d, 队尾: %d\n, DequeFront(dq), DequeBack(dq)); // 队头: 1, 队尾: 2 DequeDestroy(dq); return 0; }六、时间复杂度分析操作时间复杂度说明队头入队 push frontO(1)均摊取模运算即可队尾入队 push backO(1)均摊取模运算即可队头出队 pop frontO(1)只需移动front和size队尾出队 pop backO(1)只需减少size取队头/队尾O(1)直接根据下标访问查找任意元素O(N)双端队列不支持仅理论遍历可以看到双端队列在两端的所有操作都能做到O(1)这正是取模运算 环形复用这一设计的价值所在——不需要像普通数组那样在头部插入删除时搬移数据。七、双端队列的经典应用场景滑动窗口最大值/最小值问题这是双端队列最经典的算法应用。维护一个单调队列队列中保存的是候选最大值的下标新元素从队尾入队时先把队尾所有比它小的元素弹出因为它们不可能再成为最大值窗口滑动时再从队头判断是否需要出队整个过程均摊O(1)可以将暴力解法的O(N×K)优化到O(N)同时实现栈和队列只用一种数据结构就能按需切换成栈或队列的行为非常灵活回文判断可以两端同时向中间靠拢比较元素是否相等任务调度中的优先级插队普通任务从队尾入队排队高优先级任务可以直接从队头插入优先被处理浏览器历史记录前进后退双端队列可以同时支持从两端扩展和收缩历史记录。八、双端队列 vs 栈 vs 队列特性栈队列双端队列操作端一端两端各一种操作两端各两种操作操作原则LIFOFIFO两端均可进出常用实现数组链表循环数组 / 双向链表核心机制top指针head tail指针front size 取模运算灵活性低中高是栈和队列的超集典型应用括号匹配、DFSBFS、任务调度滑动窗口、单调队列可以说双端队列的功能覆盖了栈和队列——如果只用它的一端行为就退化成栈如果一端进一端出行为就是队列。这也是为什么STL选择用deque作为stack和queue的默认底层容器适配器模式。九、总结双端队列打破了栈只能一端操作和队列两端各只能一种操作的限制做到了两端都能自由插入删除。用循环数组实现时核心技巧就是front下标 size计数 取模运算让数组在逻辑上首尾相连从而避免了数据搬移两端操作均摊都是O(1)。如果只是简单场景直接用双向链表实现双端队列会更简单直观但如果追求更好的缓存利用率和空间紧凑性循环数组是更优的选择也是理解STLdeque底层设计思想的一把钥匙。建议实现完之后动手做一道滑动窗口最大值的算法题感受一下单调双端队列的精妙之处。如果这篇文章对你有帮助欢迎点赞收藏后续会继续更新树、二叉树等数据结构内容