企业官网建设流程全解析

前言

前面讲了栈（一端进出）和队列（一端进、一端出）。这一篇讲双端队列——顾名思义，它把栈和队列的能力结合在了一起：两端都能插入，两端都能删除。理解了双端队列，再看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->capacity

3.对应单行使用示例

// 扩容拷贝 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 Back）

void 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; }

六、时间复杂度分析

可以看到，双端队列在两端的所有操作都能做到O(1)，这正是"取模运算 + 环形复用"这一设计的价值所在——不需要像普通数组那样在头部插入删除时搬移数据。

七、双端队列的经典应用场景

• 滑动窗口最大值/最小值问题：这是双端队列最经典的算法应用。维护一个"单调队列"，队列中保存的是候选最大值的下标，新元素从队尾入队时，先把队尾所有比它小的元素弹出（因为它们不可能再成为最大值），窗口滑动时再从队头判断是否需要出队，整个过程均摊O(1)，可以将暴力解法的O(N×K)优化到O(N)；
• 同时实现栈和队列：只用一种数据结构，就能按需切换成栈或队列的行为，非常灵活；
• 回文判断：可以两端同时向中间靠拢比较元素，是否相等；
• 任务调度中的优先级插队：普通任务从队尾入队排队，高优先级任务可以直接从队头插入，优先被处理；
• 浏览器历史记录（前进+后退）：双端队列可以同时支持从两端扩展和收缩历史记录。

八、双端队列 vs 栈 vs 队列

可以说，双端队列的功能覆盖了栈和队列——如果只用它的一端，行为就退化成栈；如果一端进一端出，行为就是队列。这也是为什么STL选择用deque作为stack和queue的默认底层容器（适配器模式）。

九、总结

双端队列打破了栈"只能一端操作"和队列"两端各只能一种操作"的限制，做到了两端都能自由插入删除。用循环数组实现时，核心技巧就是front下标 +size计数 +取模运算，让数组在逻辑上"首尾相连"，从而避免了数据搬移，两端操作均摊都是O(1)。

如果只是简单场景，直接用双向链表实现双端队列会更简单直观；但如果追求更好的缓存利用率和空间紧凑性，循环数组是更优的选择，也是理解STLdeque底层设计思想的一把钥匙。建议实现完之后，动手做一道"滑动窗口最大值"的算法题，感受一下单调双端队列的精妙之处。

如果这篇文章对你有帮助，欢迎点赞收藏，后续会继续更新树、二叉树等数据结构内容！