Appearance
链式队列
2026 大纲 三（三）栈和队列的链式存储结构 · 队列部分（栈的部分见《链栈》）。
为什么链队必须有两个指针
队列的两个操作分别发生在两端：队头删、队尾插。而单链表只能从头往后走，所以想让两端都是 front 指队头一侧，rear 指队尾结点。
少一个都会有一端退化：只留 front，入队要遍历到表尾，rear，找队头同样
对照链栈记：链栈只在表头一端操作，一个
top就够、连头结点都不需要；链队在两端操作，必须两个指针，而且带头结点更划算。差异的唯一根源是"操作发生在几端"。
链队还有一个先天的好处：它没有"队满"这回事，也就天然不存在循环队列那套假溢出与判满方案——唯一的失败来源是 malloc 返回 NULL。
结构定义
c
typedef struct LinkNode {
int data;
struct LinkNode *next;
} LinkNode;
typedef struct {
LinkNode *front; // 队头指针，始终指向头结点
LinkNode *rear; // 队尾指针，指向最后一个数据结点
} LinkQueue;text
空队列: front → [头结点] ← rear （next = NULL）
非空队列: front → [头结点] → [a₁] → [a₂] → [a₃] ← rear先看一眼
把元素全部出队，盯住最后一个元素被删掉的那一瞬间 rear 指向哪里——这是本篇唯一一个必须专门处理的边界，下面会展开。
四个基本操作
c
bool InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode)); // 建头结点
if (Q->front == NULL) return false;
Q->front->next = NULL;
return true; // 两针都指头结点，与判空条件配套
}
bool QueueEmpty(LinkQueue Q) { return Q.front == Q.rear; }
bool EnQueue(LinkQueue *Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) return false;
s->data = x;
s->next = NULL; // 不能省：malloc 不清零，漏写则 rear->next 是随机值
Q->rear->next = s; // 队空时它挂在头结点后，无需特判
Q->rear = s;
return true;
}
bool DeQueue(LinkQueue *Q, int *x) {
if (Q->front == Q->rear) return false; // 队空
LinkNode *p = Q->front->next;
*x = p->data;
Q->front->next = p->next;
if (Q->rear == p) // 🔴 原队列只有一个数据结点
Q->rear = Q->front; // rear 指回头结点，恢复空队列形态
free(p);
return true;
}
bool GetHead(LinkQueue Q, int *x) {
if (Q.front == Q.rear) return false;
*x = Q.front->next->data; // 是 front->next->data，不是 front->data
return true;
}GetHead 那一行的 front->next->data 要多跳一步，因为头结点不存数据。真正的必答项是 DeQueue 里那句 if (Q->rear == p) Q->rear = Q->front;——它修的是一个会导致未定义行为的悬空指针。
🔴 漏写 rear = front 会怎样——逐步反例（想彻底弄懂这个边界就展开）
设队列中只有一个元素 front 指头结点 H，rear 指 H->next = a₁。
| 步骤 | 若漏写那一句的状态 |
|---|---|
p = front->next | p = a₁ |
front->next = p->next | H->next = NULL，链表已空 |
free(p) | |
| 结果 | front == H、rear 仍指向已释放的 front != rear，判空返回"非空" |
| 下一次入队 | 执行 rear->next = s，即向已释放内存写入——未定义行为 |
| 下一次出队 | 判空被绕过，p = front->next = NULL，随后 *x = p->data 空指针解引用 |
补上之后 rear = front = H，队列回到与 InitQueue 之后完全相同的形态。
这个边界在循环队列里根本不存在——那里 front、rear 是下标，出队只是前进一格，不会有"指向已释放内存"的问题。链式结构的边界风险来自 free，这是它与顺序结构最本质的差异之一。
不带头结点的对照写法（想看清头结点到底省了什么就展开）
front 直接指队头元素，空队列用 front == NULL 表示，入队和出队各多一个特判：
c
bool InitQueue_NH(LinkQueue *Q) { Q->front = Q->rear = NULL; return true; }
bool QueueEmpty_NH(LinkQueue Q) { return Q.front == NULL; }
bool EnQueue_NH(LinkQueue *Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) return false;
s->data = x; s->next = NULL;
if (Q->front == NULL) // 🔴 空队列：新结点既是队头也是队尾
Q->front = Q->rear = s;
else { Q->rear->next = s; Q->rear = s; }
return true;
}
bool DeQueue_NH(LinkQueue *Q, int *x) {
if (Q->front == NULL) return false;
LinkNode *p = Q->front;
*x = p->data;
Q->front = p->next;
if (Q->rear == p) Q->rear = NULL; // 🔴 删的是最后一个，两针一起归零
free(p);
return true;
}对比两种写法能看清一件事：头结点买到的是"入队不用特判空队列"，没能买到"出队不用特判删最后一个"——后者两种写法都躲不掉，只是重置目标不同（rear = front 与 rear = NULL）。以为"带头结点就不用管边界了"是个常见误解。
还有一种能把指针数量降到一个的写法：把链表做成带头结点的循环单链表，只保存 rear。 因为成环之后 rear->next 恒为头结点、rear->next->next 就是队头元素，两端仍然都能 rear 照样要重置。
变体：用带尾指针的循环单链表表示队列（只要一个指针）
把链表做成带头结点的循环单链表，只保存 rear：rear->next 是头结点， rear->next->next 是队头元素，两端操作仍都是
text
┌──────────────────────────────┐
↓ │
[头结点] → [a₁] → [a₂] → [a₃] ───┘
↑ rearc
typedef LinkNode *CQueue; // rear 指针本身就是整个队列
bool InitCQueue(CQueue *rear) {
LinkNode *h = (LinkNode *)malloc(sizeof(LinkNode));
if (h == NULL) return false;
h->next = h; // 自己指向自己：空队列
*rear = h;
return true;
}
bool CQueueEmpty(CQueue rear) { return rear->next == rear; }
bool EnCQueue(CQueue *rear, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) return false;
s->data = x;
s->next = (*rear)->next; // (*rear)->next 永远是头结点，新结点自动环回去
(*rear)->next = s; // 这两句写反会造成自环
*rear = s;
return true;
}
bool DeCQueue(CQueue *rear, int *x) {
if ((*rear)->next == *rear) return false;
LinkNode *h = (*rear)->next, *p = h->next;
*x = p->data;
h->next = p->next;
if (*rear == p) *rear = h; // 🔴 同样躲不掉
free(p);
return true;
}循环链表省掉的是一个指针，不是那个边界。
链队 vs 循环队列
| 对比项 | 循环队列（顺序） | 链式队列 |
|---|---|---|
| 容量 | 预分配 MaxSize，固定 | 按需分配，无固定上限 |
| 队满 | 会发生（三种判别方案见对应篇） | 不会，只可能 malloc 失败 |
| 假溢出 | 靠取模绕回解决 | 天然不存在 |
| 判空 | 方案一 front == rear（下标比较） | front == rear（地址比较）或 front == NULL |
| 是否牺牲单元 | 方案一需要，容量 MaxSize-1 | 不需要 |
| 指针个数 | 2 个下标 | 2 个指针（或 1 个 rear + 循环链表） |
| 存储密度 | int 与指针各 4 字节时为 | |
| 求队长 | ||
| 缓存性能 | 好（连续存储） | 差（结点分散） |
| 适用场景 | 容量可预估 | 容量波动大或不可预估 |
两边的
front == rear长得一样、含义完全不同：循环队列比的是下标、且是牺牲一格换来的；链队比的是地址、且链队根本没有"满"，所以不存在二义性。
入队、出队、判空、取队头都是
考点速记
三条会被反复调用的结论：
- 两个指针是结构性要求，不是实现偏好：少一个就有一端退化成
。 if (rear == p) rear = front;是出队的必答项，它修的是一个会导致未定义行为的悬空指针；带不带头结点都躲不掉。- 链队没有"满"，所以
front == rear不存在循环队列那种二义性。
这一节在真题里被考过的形式（下方「真题练习」逐题对应）：考队列的题很少考链式实现的代码，考的是"什么时候该用队列"和"多个队列协同能得到什么输出"：
- 给一个应用场景，问该用什么逻辑结构：典型是"主机与打印机速度不匹配，中间的缓冲区应该是什么结构"。判据是到达顺序必须被保持、不允许插队，答案是队列。
- 多条 FIFO 通道的调度：比如"入口到出口之间有
条只能单向通行的轨道，列车按给定次序驶入、要求按 驶出，问 至少是多少"。每条轨道就是一个队列，关键性质是同一条轨道内先进的必先出，所以一条轨道上的车号必须是递增的；问题就变成"把给定序列拆成最少多少条递增子序列"。 - 队列与栈组合，问哪个输出序列得不到：题面给"出队直接输出 / 出队入栈 / 出栈输出"三种操作，本质仍是模拟，只是同时维护一个队列和一个栈。
- 循环队列的指针约定：这类题的落点在循环队列那一篇。
易错：出队时忘了
rear可能悬空。 删掉最后一个数据结点后必须把rear重置回头结点（不带头结点时置NULL）。
易错：取队头写成
front->data。 带头结点时头结点不存数据，要写front->next->data。
易错：入队时忘了
s->next = NULL。malloc不清零，漏写会让新的队尾结点带着一个随机指针。
教材出处
- 链队的存储结构（
QNode+LinkQueue，含front/rear两个指针）与 "给链队添加一个头结点，并令头指针始终指向头结点"的口径，以及 "若用户无法预估所用队列的最大长度，则宜采用链队"： 严蔚敏《数据结构（C 语言版）》（第 2 版）p73「3.5.3 链队——队列的链式表示和实现」 - 入队算法 3.17（分配结点 → 置数据域 → 插入队尾 → 修改队尾指针）：同书 p74
- 出队算法 3.18 与其第 ④ 步"判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值， 指向头结点"，以及正文"在链队出队操作时还要考虑当队列中最后一个元素被删后， 队列尾指针也丢失了"；取队头算法 3.19：同书 p75
相关知识
循环队列（同一逻辑结构的顺序实现）｜ 链栈（同属三（三），对比可看清"操作端数"如何决定指针个数）｜ 栈和队列的基本概念（队列 ADT 与出队序列性质）｜ 单链表（链队的入队出队就是尾插与删首结点）｜ 广度优先搜索、层次遍历（队列的两个典型使用者）