C语言双端队列实现与优化指南

1. 双端队列：C语言数据结构中的瑞士军刀

双端队列（Deque）这个数据结构在C语言中的地位，就像厨房里的多功能料理机——它既能当普通队列用（FIFO），又能当栈使（LIFO），还能两头同时操作。我在实际项目中用过不下十种数据结构实现，但双端队列绝对是使用频率最高的前三位。

为什么说它是C语言学习者的必修课？因为实现一个健壮的双端队列，你需要同时掌握：

• 指针操作的艺术
• 内存管理的精髓
• 时间复杂度控制的技巧
• 泛型设计的思路

下面这个实现版本，是我在多个商业项目中打磨出来的，包含了动态扩容、安全校验、内存回收等工程级特性。不同于教科书上的玩具代码，这个实现可以直接嵌入你的项目中使用。

2. 核心结构设计：双向链表与元数据管理

2.1 节点结构设计

双端队列的核心在于它的双向链表节点设计。每个节点需要保存：

1. 数据指针（泛型设计的关键）
2. 前驱节点指针
3. 后继节点指针

c复制typedef struct deque_node {
    void *data;                  // 泛型数据指针
    struct deque_node *next;     // 后驱节点
    struct deque_node *previous; // 前驱节点
} deque_node;

注意：使用void*实现泛型是C语言的经典做法，但需要特别注意类型安全。在实际项目中，建议配合assert进行运行时检查。

2.2 队列元数据结构

管理整个队列需要维护以下元数据：

• 头尾指针：快速访问两端
• 当前大小：O(1)时间获取元素数量
• 容量：触发扩容的阈值
• 元素大小：用于内存分配和拷贝

c复制typedef struct deque {
    struct deque_node *front;  // 队头指针
    struct deque_node *rear;   // 队尾指针
    size_t size;              // 当前元素个数
    size_t capacity;          // 容量阈值
    size_t elem_size;         // 单个元素字节数
} deque;

3. 基础操作实现详解

3.1 初始化与销毁

初始化时需要特别注意参数校验和默认值设置：

c复制int deque_init(deque *dq, size_t elem_size) {
    if (dq == NULL || elem_size == 0) {
        return -1;  // 错误码：无效参数
    }
    
    dq->front = NULL;
    dq->rear = NULL;
    dq->size = 0;
    dq->capacity = 8;  // 经验值：初始容量设为8
    dq->elem_size = elem_size;
    
    return 0;  // 成功
}

销毁队列时需要递归释放所有节点：

c复制void deque_destroy(deque *dq) {
    if (dq == NULL) return;
    
    deque_node *current = dq->front;
    while (current != NULL) {
        deque_node *next = current->next;
        free(current->data);  // 先释放数据内存
        free(current);        // 再释放节点本身
        current = next;
    }
    
    dq->front = dq->rear = NULL;
    dq->size = 0;
}

3.2 动态扩容机制

当元素数量达到容量阈值时，自动扩容为原来的2倍：

c复制static int deque_expand(deque *dq) {
    if (dq->size < dq->capacity) {
        return 0;  // 无需扩容
    }
    
    dq->capacity *= 2;  // 双倍扩容策略
    return 0;
}

实战技巧：在内存敏感的场景，可以考虑1.5倍扩容（如C++ vector的实现），这能减少内存浪费但会增加扩容频率。

4. 核心操作：插入与删除

4.1 头部插入实现

c复制int dq_push_front(deque *dq, const void *value) {
    // 参数校验
    if (dq == NULL || value == NULL) return -1;
    
    // 检查扩容
    if (dq->size >= dq->capacity) {
        if (deque_expand(dq) != 0) return -1;
    }
    
    // 创建新节点
    deque_node *node = malloc(sizeof(deque_node));
    if (node == NULL) return -1;
    
    node->data = malloc(dq->elem_size);
    if (node->data == NULL) {
        free(node);
        return -1;
    }
    
    // 拷贝数据
    memcpy(node->data, value, dq->elem_size);
    
    // 链接节点
    if (dq->front == NULL) {  // 空队列情况
        node->next = NULL;
        node->previous = NULL;
        dq->front = node;
        dq->rear = node;
    } else {  // 非空队列
        node->next = dq->front;
        node->previous = NULL;
        dq->front->previous = node;
        dq->front = node;
    }
    
    dq->size++;
    return 0;
}

4.2 尾部删除实现

c复制int dq_pop_back(deque *dq, void *value) {
    // 参数校验
    if (dq == NULL || dq->size == 0 || value == NULL) {
        return -1;
    }
    
    // 保存待删除节点
    deque_node *node = dq->rear;
    
    // 更新队列状态
    if (dq->size == 1) {  // 最后一个元素
        dq->front = NULL;
        dq->rear = NULL;
    } else {
        dq->rear = node->previous;
        dq->rear->next = NULL;
    }
    
    // 拷贝数据并释放内存
    memcpy(value, node->data, dq->elem_size);
    free(node->data);
    free(node);
    
    dq->size--;
    return 0;
}

5. 高级特性与优化技巧

5.1 迭代器模式实现

为方便遍历，可以实现简单的迭代器：

c复制typedef struct {
    deque *dq;
    deque_node *current;
} deque_iterator;

deque_iterator deque_begin(deque *dq) {
    return (deque_iterator){dq, dq->front};
}

int deque_next(deque_iterator *it, void *value) {
    if (it->current == NULL) return -1;
    
    memcpy(value, it->current->data, it->dq->elem_size);
    it->current = it->current->next;
    return 0;
}

使用示例：

c复制deque_iterator it = deque_begin(&dq);
int value;
while (deque_next(&it, &value) == 0) {
    printf("%d ", value);
}

5.2 内存池优化

频繁的malloc/free会影响性能，可以考虑使用内存池：

c复制#define POOL_SIZE 1024

typedef struct {
    deque_node nodes[POOL_SIZE];
    int used[POOL_SIZE];
    int free_count;
} deque_node_pool;

// 初始化时预分配所有节点
void pool_init(deque_node_pool *pool) {
    memset(pool-