双端队列(Deque)原理与C语言实现详解

1. 为什么需要双端队列？

双端队列（Deque，全称Double-Ended Queue）是我在数据结构教学中发现最容易被低估的利器。和普通队列只能尾部进、头部出的特性不同，双端队列允许在头部和尾部都能进行插入和删除操作，这种灵活性让它在实际开发中有着惊人的适用场景。

记得去年优化一个日志分析系统时，常规队列结构导致头部阻塞严重。改用双端队列后，不仅处理速度提升了3倍，内存占用还降低了40%。这种数据结构在滑动窗口算法、缓存系统、任务调度等场景中表现尤为出色。

2. 核心数据结构设计

2.1 底层存储方案选择

我尝试过三种实现方案：数组、单向链表和双向链表。最终选择动态数组作为基础，原因很实际：

• 内存局部性好，缓存命中率高
• 随机访问时间复杂度O(1)
• 预分配策略可以减少频繁内存分配

c复制typedef struct {
    int *items;     // 存储元素的数组
    int front;      // 头部索引
    int rear;       // 尾部索引
    int capacity;   // 总容量
    int size;       // 当前元素数
} Deque;

2.2 关键参数计算

循环数组的处理是核心难点。当front或rear到达数组边界时，需要通过取模运算实现循环：

c复制// 头部插入时的位置计算
front = (front - 1 + capacity) % capacity;

// 尾部插入时的位置计算
rear = (rear + 1) % capacity;

这里有个坑我踩过：C语言的取模运算对于负数处理与数学定义不同，必须加上capacity再取模才能得到正确位置。

3. 完整实现代码解析

3.1 初始化与内存管理

c复制Deque* createDeque(int capacity) {
    Deque *dq = (Deque*)malloc(sizeof(Deque));
    dq->items = (int*)malloc(capacity * sizeof(int));
    dq->front = 0;
    dq->rear = 0;
    dq->