链式队列：高效实现O(1)入队出队

引言

在之前的文章中，我们系统学习了栈结构（顺序栈和链栈）。栈是"后进先出"（LIFO）的结构，而今天要讲解的队列（Queue）则是"先进先出"（FIFO，First In First Out）的结构。

队列在计算机科学中应用极为广泛：操作系统的任务调度、消息队列、打印队列、网络数据包缓冲……几乎所有需要"排队处理"的场景都离不开队列。

本文将详细讲解链式队列的完整实现。链式队列使用链表节点动态存储元素，配合头尾指针实现 O(1) 的入队和出队操作。

第一部分：链式队列的设计原理

一、核心数据结构

链式队列由两个结构体组成：

// 1. 节点结构体 typedef struct Queuenode { ElempType val; // 数据域 struct Queuenode* next; // 指针域，指向下一个节点 } Queuenode, *PQueuenode; // 2. 队列管理结构体（带头结点） typedef struct LinkQueue { PQueuenode front; // 队头指针（指向头结点） PQueuenode rear; // 队尾指针（指向最后一个节点） } LinkQueue, *PLinkQueue;

二、关键设计：头结点 + 双指针

三、队列状态判断

四、为什么需要头结点和尾指针

第二部分：初始化与销毁

一、创建节点

PQueuenode buynode(ElempType val) { PQueuenode p = (PQueuenode)malloc(sizeof(Queuenode)); if (p == NULL) return NULL; p->next = NULL; p->val = val; return p; }

二、初始化（带头结点）

void InitLinkQueue(PLinkQueue ps) { assert(ps != NULL); // 创建头结点 PQueuenode p = buynode(0); if (p == NULL) return; // 空队列：front 和 rear 都指向头结点 ps->rear = p; ps->front = p; }

初始化后的状态：

三、销毁

void Destroy(PLinkQueue ps) { assert(ps != NULL); if (Isempty(ps)) return; // 逐个释放所有节点（包括头结点） while (ps->front != NULL) { PQueuenode p = ps->front; ps->front = p->next; free(p); } // 指针置空 ps->rear = NULL; }

清空 vs 销毁：

// 清空：保留头结点，只释放数据节点 void Clear(PLinkQueue ps) { assert(ps != NULL); if (Isempty(ps)) return; while (ps->front->next != NULL) { PQueuenode p = ps->front->next; ps->front->next = p->next; free(p); } ps->rear = ps->front; // rear 回到头结点 } // 销毁：释放所有节点，包括头结点 void Destroy(PLinkQueue ps) { // 释放所有节点，指针置 NULL }

第三部分：核心操作实现

一、入队（Push）

bool Push(PLinkQueue ps, ElempType val) { assert(ps != NULL); // 1. 创建新节点 PQueuenode p = buynode(val); if (p == NULL) return false; // 2. 插入到队尾 ps->rear->next = p; // 当前最后一个节点的 next 指向新节点 ps->rear = p; // rear 后移 return true; }

入队过程图解：

入队的特殊情况：

// 空队列入队：
// 入队前：front == rear == 头结点
// 入队后：front == 头结点, rear == 新节点
// 代码逻辑完全适用，无需特殊处理！

二、出队（Pop）

bool Pop(PLinkQueue ps, ElempType* pval) { assert(ps != NULL && pval != NULL); if (Isempty(ps)) return false; // 1. 获取队头节点（头结点后的第一个节点） PQueuenode p = ps->front->next; // 2. 获取数据 *pval = p->val; // 3. 跳过被删除的节点 ps->front->next = p->next; // 4. 特殊处理：如果删除的是最后一个节点，rear 要回退 if (p == ps->rear) { ps->rear = ps->front; } // 5. 释放节点 free(p); return true; }

注意：原代码中缺少了rear回退的特殊处理。当队列只有一个元素时，出队后rear应该指向头结点。

修正后的代码：

bool Pop(PLinkQueue ps, ElempType* pval) { assert(ps != NULL && pval != NULL); if (Isempty(ps)) return false; PQueuenode p = ps->front->next; *pval = p->val; ps->front->next = p->next; // ★ 关键：删除的是最后一个节点时，更新 rear if (p == ps->rear) { ps->rear = ps->front; } free(p); return true; }

三、获取队头和队尾

// 获取队头元素 bool Getfront(PLinkQueue ps, ElempType* pval) { assert(ps != NULL); if (Isempty(ps)) return false; *pval = ps->front->next->val; // 头结点后的第一个节点 return true; } // 获取队尾元素 bool Getrear(PLinkQueue ps, ElempType* pval) { assert(ps != NULL); if (Isempty(ps)) return false; *pval = ps->rear->val; // 直接通过 rear 指针获取 return true; }

四、判空

bool Isempty(const PLinkQueue ps) { assert(ps != NULL); return ps->front == ps->rear; }

五、获取元素个数

int Getsize(const PLinkQueue ps) { assert(ps != NULL); int n = 0; for (Queuenode* p = ps->front->next; p != NULL; p = p->next) { n++; } return n; }

注意：这里的获取大小是 O(n) 遍历。如果想 O(1)，可以在LinkQueue结构体中添加cursize成员。

第四部分：完整操作一览

时间复杂度分析

操作要点速查

第六部分：链式队列 vs 顺序队列

总结

一、链式队列的核心原理

二、操作复杂度速查

三、一句话记忆

链式队列用 front 和 rear 两个指针分别指向头结点和尾节点，入队时在 rear 后面插入并更新 rear，出队时删除 front 后面的节点，实现 O(1) 的入队和出队操作。出队时如果删除了最后一个节点，必须将 rear 回退到头结点。