Appearance
链式队列
核心思想
链式队列的核心特点：
- FIFO 原则：只能从队尾（rear）插入，从队头（front）删除
- 两个指针：
front指向队头结点（或头结点），rear指向队尾结点 - 带头结点：通常设置一个头结点，使空队列和非空队列的操作统一
结点与队列的定义：
c
// 链式队列结点
typedef struct LinkNode {
int data;
struct LinkNode *next;
} LinkNode;
// 链式队列（带头结点）
typedef struct {
LinkNode *front; // 队头指针，指向头结点
LinkNode *rear; // 队尾指针，指向最后一个元素
} LinkQueue;队列状态示意：
空队列: front -> [头结点] <- rear
next=NULL
非空队列: front -> [头结点] -> [a₁] -> [a₂] -> [a₃] <- rear
next=NULL判空条件：Q.front == Q.rear（即 front 和 rear 都指向头结点）。
交互可视化
通过下方的交互动画，你可以逐步观察链式队列的执行过程：
操作详解
入队操作
在队尾插入新元素，需要修改 rear 指针。
关键步骤：
- 创建新结点，赋值
- 将新结点插入到队尾结点之后
rear指向新结点
c
// 入队（带头结点）
bool EnQueue(LinkQueue *Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) return false; // 内存分配失败
s->data = x;
s->next = NULL;
Q->rear->next = s; // 新结点插入到 rear 之后
Q->rear = s; // 修改队尾指针
return true;
}出队操作
删除队头元素（头结点之后的第一个结点），需要注意队列中只剩一个元素时要同时修改 rear。
关键步骤：
- 判断队列是否为空
- 取出队头结点（头结点的下一个结点）
- 修改头结点的
next指针 - 若删除后队列为空，需将
rear重新指向头结点 - 释放被删结点，表长减 1
c
// 出队（带头结点）
bool DeQueue(LinkQueue *Q, int *x) {
if (Q->front == Q->rear) return false; // 队空
LinkNode *p = Q->front->next; // p 指向队头元素
*x = p->data;
Q->front->next = p->next; // 修改头结点 next
if (Q->rear == p) // 若原队列只有一个结点
Q->rear = Q->front; // rear 指回头结点
free(p);
return true;
}复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 入队 | O(1) | 直接在 rear 后插入 |
| 出队 | O(1) | 直接删除 front 后的结点 |
| 取队头元素 | O(1) | 访问 front->next->data |
| 判空 | O(1) | 比较 front 与 rear |
空间复杂度：O(n)，每个元素需要额外存储一个指针域。
易错：带头结点的链式队列判空是
front == rear（front 和 rear 都指向头结点）；不带头结点时判空是front == NULL。两种方式的入队、出队操作有细微差别，408 需要区分。
考研高频考点
- ⭐ 链式队列的判空条件：
Q.front == Q.rear（选择题高频） - ⭐ 出队时只剩一个元素需要同时修改
rear指针（代码题易错点） - ⭐ 链式队列 vs 循环队列的优缺点对比（简答题常考）
- ⭐ 带头结点与不带头结点的链式队列操作差异（选择题/代码题）
- 队列在层序遍历（BFS）中的应用（算法题必备）
- 队列的 FIFO 特性与栈的 LIFO 特性对比（概念题）
相关知识
- 循环队列是队列的顺序存储实现，通过取模运算解决假溢出问题；链式队列天然不存在假溢出
- 顺序栈与链式队列的对比体现了栈（LIFO）和队列（FIFO）的本质区别
- BFS（广度优先搜索）是队列最重要的应用场景——每一层的结点依次入队、出队，驱动逐层遍历