C语言双端队列详解（从零开始实现高效双端队列）

什么是双端队列？

双端队列是一种允许在两端进行插入和删除操作的线性数据结构。它结合了栈和队列的特性：

• 前端（Front）可以入队（push_front）和出队（pop_front）
• 后端（Rear/Back）也可以入队（push_back）和出队（pop_back）

为什么使用 C 语言实现双端队列？

C 语言贴近底层，能让你深入理解内存管理和指针操作。掌握C语言数据结构是成为优秀程序员的重要一步。而双端队列实现正是锻炼逻辑思维与编码能力的绝佳练习。

实现思路：基于动态数组

我们将使用动态分配的数组来实现双端队列，并维护两个指针：front 和 rear。为提高效率，我们采用“循环数组”方式避免频繁移动元素。

定义双端队列结构

#include <stdio.h>#include <stdlib.h>#define INIT_CAPACITY 4typedef struct {    int* data;          // 动态数组存储元素    int front;          // 队首索引    int rear;           // 队尾索引    int size;           // 当前元素个数    int capacity;       // 数组容量} Deque;

初始化双端队列

Deque* createDeque() {    Deque* dq = (Deque*)malloc(sizeof(Deque));    if (!dq) return NULL;        dq->data = (int*)malloc(INIT_CAPACITY * sizeof(int));    if (!dq->data) {        free(dq);        return NULL;    }        dq->front = 0;    dq->rear = 0;    dq->size = 0;    dq->capacity = INIT_CAPACITY;        return dq;}

扩容函数（当空间不足时）

void resize(Deque* dq) {    int new_capacity = dq->capacity * 2;    int* new_data = (int*)malloc(new_capacity * sizeof(int));    if (!new_data) return;        // 将原数据按顺序复制到新数组    for (int i = 0; i < dq->size; i++) {        new_data[i] = dq->data[(dq->front + i) % dq->capacity];    }        free(dq->data);    dq->data = new_data;    dq->front = 0;    dq->rear = dq->size;    dq->capacity = new_capacity;}

核心操作：前端插入（push_front）

void push_front(Deque* dq, int value) {    if (dq->size == dq->capacity) {        resize(dq);    }    dq->front = (dq->front - 1 + dq->capacity) % dq->capacity;    dq->data[dq->front] = value;    dq->size++;}

核心操作：后端插入（push_back）

void push_back(Deque* dq, int value) {    if (dq->size == dq->capacity) {        resize(dq);    }    dq->data[dq->rear] = value;    dq->rear = (dq->rear + 1) % dq->capacity;    dq->size++;}

前端弹出（pop_front）

int pop_front(Deque* dq) {    if (dq->size == 0) {        printf("Error: Deque is empty!\n");        exit(1);    }    int value = dq->data[dq->front];    dq->front = (dq->front + 1) % dq->capacity;    dq->size--;    return value;}

后端弹出（pop_back）

int pop_back(Deque* dq) {    if (dq->size == 0) {        printf("Error: Deque is empty!\n");        exit(1);    }    dq->rear = (dq->rear - 1 + dq->capacity) % dq->capacity;    int value = dq->data[dq->rear];    dq->size--;    return value;}

完整测试示例

int main() {    Deque* dq = createDeque();        push_back(dq, 10);    push_back(dq, 20);    push_front(dq, 5);    push_front(dq, 1);        // 当前双端队列：[1, 5, 10, 20]        printf("%d\n", pop_front(dq)); // 输出 1    printf("%d\n", pop_back(dq));  // 输出 20        // 释放内存    free(dq->data);    free(dq);        return 0;}

总结

通过本教程，你已经掌握了如何用 C 语言从零实现一个功能完整的双端队列。这不仅加深了你对数据结构教程的理解，也提升了你的 C 编程能力。双端队列在滑动窗口、回文判断等算法中非常有用，建议你动手敲一遍代码，真正掌握这一重要数据结构！

关键词回顾：C语言双端队列、双端队列实现、数据结构教程、C语言数据结构