当前位置：首页 > news >正文

C语言双端队列完整实现：一行代码吃透头尾操作，算法效率拉满

news 2026/5/26 2:39:56

一、为什么C语言实现双端队列，是数据结构的必学天花板？

在C语言数据结构里，队列、栈都是基础中的基础，但真正能把灵活度、效率、内存管理三者揉到一起的，还得是双端队列（deque）。

普通队列只能一头进一头出，栈只能先进后出，而双端队列可以两头插、两头删，既兼容队列FIFO，又支持栈LIFO，堪称数据结构里的“全能选手”。

很多人学数据结构，只停留在理论，一到C语言手写就卡壳：指针不会用、内存容易漏、扩容逻辑写不明白。而今天这套完整实现，把双向链表、动态扩容、泛型设计、安全释放全部打通，所有操作全是O(1)时间复杂度，工程级可用，看完就能直接写进项目里。

它不是玩具代码，而是能真正用于面试、作业、实际开发的稳健实现。

二、核心拆解：双端队列结构与完整代码实现1. 双端队列核心结构设计

双端队列的关键，是用双向链表节点串联，再用一个总结构管理头尾、大小、容量和元素大小，实现与类型无关的通用队列。

// 双向链表节点 typedef struct deque_node { void *data; // 数据指针 struct deque_node *next; // 后驱节点 struct deque_node *previous; // 前驱节点 } deque_node; // 双端队列总结构 typedef struct deque { struct deque_node *front; // 队头 struct deque_node *rear; // 队尾 size_t size; // 当前元素个数 size_t capacity; // 容量 size_t elem_size; // 单个元素大小 } deque;

2. 队列初始化

先做参数安全校验，再给默认容量，从根源避免野指针和非法访问。

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

3. 头部插入 & 尾部插入

支持队头加元素、队尾加元素，满了自动扩容2倍，不用手动管理。

// 头部插入 int dq_push_front(deque *dq, const void *value) { if (dq == NULL || value == NULL) return -1; if (dq->size >= dq->capacity) dq->capacity *= 2; deque_node *node = malloc(sizeof(deque_node)); node->data = malloc(dq->elem_size); 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; } // 尾部插入 int dq_push_back(deque *dq, const void *value) { if (dq == NULL || value == NULL) return -1; if (dq->size >= dq->capacity) dq->capacity *= 2; deque_node *node = malloc(sizeof(deque_node)); node->data = malloc(dq->elem_size); 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 = NULL; node->previous = dq->rear; dq->rear->next = node; dq->rear = node; } dq->size++; return 0; }

4. 头部删除 & 尾部删除

删完自动把数据拷贝出来，并安全释放内存，不产生内存泄漏。

// 头部删除 int dq_pop_front(deque *dq, void *value) { if (dq == NULL || dq->size == 0 || value == NULL) return -1; deque_node *node = dq->front; dq->front = dq->front->next; dq->front->previous = NULL; dq->size--; memcpy(value, node->data, dq->elem_size); free(node->data); free(node); return 0; } // 尾部删除 int dq_pop_back(deque *dq, void *value) { if (dq == NULL || dq->size == 0 || value == NULL) return -1; deque_node *node = dq->rear; dq->rear = dq->rear->previous; dq->rear->next = NULL; dq->size--; memcpy(value, node->data, dq->elem_size); free(node->data); free(node); return 0; }

5. 查看队头队尾 & 工具函数

只看不删，方便判断、遍历、调试。

// 查看队头 int dq_peek_front(deque *dq, void *value) { if (dq == NULL || dq->size == 0 || value == NULL) return -1; memcpy(value, dq->front->data, dq->elem_size); return 0; } // 查看队尾 int dq_peek_back(deque *dq, void *value) { if (dq == NULL || dq->size == 0 || value == NULL) return -1; memcpy(value, dq->rear->data, dq->elem_size); return 0; } // 判断空 int dq_is_empty(deque *dq) { if (dq == NULL) return -1; return dq->size == 0 ? 0 : 1; } // 获取大小 int dq_size(deque *dq) { if (dq == NULL) return -1; return dq->size; }

6. 效率总结

这套双端队列所有核心操作：

时间复杂度：O(1)

空间复杂度：O(1)

效率稳定，适合高频操作场景。

三、辩证思考：这样实现双端队列，真的完美吗？

这套实现非常经典、完整，但放在真实开发里，依然有值得权衡的地方。

从优点看：

但也有客观短板：

这不是代码的问题，而是数据结构本身的取舍：你要灵活，就要牺牲一点连续内存；你要O(1)头尾操作，就很难兼顾极致紧凑。

真正优秀的程序员，不是只会抄代码，而是知道什么时候用链表deque，什么时候用数组deque。

四、现实意义：学会这套，对C语言开发者意味着什么？