C / C++ / 系统课时
用链表实现动态队列
用链表实现动态队列
数组队列容量固定或需要扩容时,链式队列可以按需申请节点。关键不是“把链表接起来”这么简单,而是同时维护队头和队尾,并正确处理第一次入队、最后一次出队这两个会改变空队列状态的边界。
学习目标
- 理解链式队列中头指针、尾指针与 FIFO 规则的对应关系
- 能用 C 语言实现入队、出队和释放操作
- 能正确处理空队列、单节点队列以及内存申请失败
头尾指针各负责什么
链式队列通常让 front 指向队头节点,让 rear 指向队尾节点。出队只从 front 删除,入队只在 rear 后追加,因此两种操作都不需要从头遍历链表,正常情况下时间复杂度都是 。
空队列时有一个很重要的不变量:front == NULL 与 rear == NULL 必须同时成立。第一次入队后,两者都指向唯一节点;最后一个节点出队后,也必须把两者同时恢复为 NULL。

完整实现
下面的示例把队列状态封装在 Queue 中。enqueue 负责创建并挂接新节点,dequeue 负责移除队头,并通过返回值区分“成功出队”和“队列为空”。
c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
} Queue;
void init_queue(Queue *queue) {
queue->front = NULL;
queue->rear = NULL;
}
int enqueue(Queue *queue, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) {
return 0;
}
node->value = value;
node->next = NULL;
if (queue->rear == NULL) {
// 空队列第一次入队:队头和队尾都必须指向新节点。
queue->front = node;
queue->rear = node;
} else {
queue->rear->next = node;
queue->rear = node;
}
return 1;
}
int dequeue(Queue *queue, int *out_value) {
if (queue->front == NULL) {
return 0;
}
Node *old_front = queue->front;
*out_value = old_front->value;
queue->front = old_front->next;
if (queue->front == NULL) {
// 删除最后一个节点后,rear 不能继续指向已释放内存。
queue->rear = NULL;
}
free(old_front);
return 1;
}
void destroy_queue(Queue *queue) {
int ignored;
while (dequeue(queue, &ignored)) {
}
}
int main(void) {
Queue queue;
init_queue(&queue);
if (!enqueue(&queue, 10) ||
!enqueue(&queue, 20) ||
!enqueue(&queue, 30)) {
fprintf(stderr, "enqueue failed\n");
destroy_queue(&queue);
return 1;
}
int value;
while (dequeue(&queue, &value)) {
printf("%d\n", value);
}
printf("empty=%s\n",
queue.front == NULL && queue.rear == NULL ? "yes" : "no");
return 0;
}预期输出
text
10
20
30
empty=yes输出顺序验证了 FIFO:先进入的 10 最先离开。最后的 empty=yes 则验证了最后一次出队后,front 和 rear 都已经恢复为空指针。
两个最容易写错的边界
第一次入队时,不能只修改 rear。如果原队列为空,front 也必须指向新节点,否则后续出队会误判为空。
最后一次出队时,不能只让 front 变成 NULL。旧的 rear 仍指向已经 free 的节点,会形成悬空指针;下一次入队若继续访问 rear->next,就可能触发未定义行为。
什么时候适合链式队列
当元素数量难以预估、希望按需增长,而且能够接受每个节点额外保存一个指针的开销时,链式队列很合适。它不需要整体扩容,也不要求一段连续内存。
如果容量上限明确、元素数量很多且追求更好的缓存局部性,循环数组队列通常更省内存、更快。选择链式结构的核心理由,是动态容量与稳定的 头尾操作,而不是“链表一定比数组高级”。
按自己的节奏,确认真正理解。