前言承接上一篇顺序栈的实现本篇完成「先进先出」的链式队列手写。 全文围绕三个核心问题展开为什么队列优先选单链表实现、frontrear双指针的设计意义、size成员的价值同时附上完整可运行代码与真实实现过程中的踩坑复盘。本文全部代码已托管至 Gitee代码采用头文件与实现文件分离的模块化写法测试用例覆盖空队列、单节点、多次入出队等全部边界场景可直接拉取本地编译调试。Gitee 仓库地址数据结构/8.17 队列练习Queue · Luminous/Code_2026 - 码云 - 开源中国一、队列基础先进先出的线性表队列是操作受限的线性表仅允许在队尾rear插入、队头front删除遵循FIFOFirst In First Out先进先出规则。典型应用场景二叉树层序遍历、图的广度优先搜索BFS操作系统任务调度、请求排队生产者消费者模型、消息缓冲区二、实现选型为什么队列更适合用单链表实现队列有「顺序表」和「链表」两条路线选择单链表并非习惯而是由队列的操作特性决定的。2.1 顺序表实现队列的天然缺陷如果用数组实现队列会直接撞上「头删低效」的问题普通数组队头删除需要整体搬移后续元素时间复杂度O(N)效率极低循环队列通过双下标规避搬移但又引入新问题——容量固定无法动态扩容、「队空/队满」边界判断繁琐、存在空间浪费本质上顺序表是在弥补「头删」的天生短板需要额外处理大量环形逻辑。2.2 单链表的天然适配性单链表的特性刚好匹配队列的操作模式队头删除 链表头删天然O(1)队尾插入 链表尾插只要增加一个尾指针rear也能做到O(1)动态申请节点无固定容量上限元素数量不确定的场景更友好2.3 为什么不用双向链表双向链表虽然自带尾指针但每个节点多一个prev指针会额外占用内存。队列仅涉及头删、尾插完全不需要向前遍历双向链表属于冗余设计。所以单链表 尾指针是实现队列性价比最高的方案。三、链式队列的结构设计采用「节点结构体 队列管理结构体」的分层设计职责分离更清晰。3.1 节点结构体typedef struct QueueNode { QDataType data; // 存储数据 struct QueueNode* next; // 指向后继节点 } QueueNode;与普通单链表节点完全一致负责存储数据与维系链表关系。3.2 队列管理结构体typedef struct Queue { QueueNode* front; // 队头指针指向第一个节点 QueueNode* rear; // 队尾指针指向最后一个节点 int size; // 记录有效元素个数 } Queue;三个成员共同描述队列的完整状态front服务队头出队、取队头元素rear服务队尾入队、取队尾元素将尾插从 O(N) 优化到 O(1)size记录元素总数是性价比极高的可选优化四、深度解析size 成员的设计价值size不是链式队列的必需成员但属于「极小成本换极大收益」的经典设计核心价值有三点长度查询从 O(N) 降为 O(1)无size时求队列长度必须从头遍历链表加入size后入队1、出队-1查询直接返回数值频繁查询长度的场景性能提升显著。辅助校验队列状态size是独立于指针的第二维度状态。正常情况下size 0必然对应front NULL rear NULL。调试时如果两者不一致可以快速定位出入队/出队/销毁操作的状态维护错误。空间成本极低仅占用一个int的内存通常4字节换来常数级的查询效率与更清晰的代码语义。注意size并不天然比指针判空更安全。如果代码本身维护错误size同样会失真。核心是始终维护队列的不变量空队列时front NULL rear NULL size 0。五、完整代码实现采用模块化拆分Queue.h声明接口Queue.c实现逻辑test.c测试验证。5.1 Queue.h 头文件#pragma once #includestdio.h #includestdlib.h #includeassert.h typedef int QDataType; // 队列节点 typedef struct QueueNode { QDataType data; struct QueueNode* next; } QueueNode; // 队列管理结构体 typedef struct Queue { QueueNode* front; QueueNode* rear; int size; } Queue; void QueueInit(Queue* q); // 初始化 void QueuePush(Queue* q, QDataType data); // 队尾入队 void QueuePop(Queue* q); // 队头出队 QDataType QueueFront(Queue* q); // 获取队头元素 QDataType QueueBack(Queue* q); // 获取队尾元素 int QueueSize(Queue* q); // 获取元素个数 int QueueEmpty(Queue* q); // 判空 void QueueDestroy(Queue* q); // 销毁队列5.2 Queue.c 实现文件#includeQueue.h // 初始化队列 void QueueInit(Queue* q) { assert(q); q-front NULL; q-rear NULL; q-size 0; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); QueueNode* Newnode (QueueNode*)malloc(sizeof(QueueNode)); if (Newnode NULL) { printf(malloc fail\n); return; } // 先初始化节点再接入链表 Newnode-next NULL; Newnode-data data; if (q-front NULL) { // 空队列首次入队头尾同时指向新节点 q-front Newnode; q-rear Newnode; } else { // 非空队列尾插后更新尾指针 q-rear-next Newnode; q-rear Newnode; } q-size; } // 队头出队列 void QueuePop(Queue* q) { assert(q q-front); if (q-front ! q-rear) { // 多个节点头指针后移释放旧头 QueueNode* node q-front; q-front q-front-next; free(node); } else { // 仅剩最后一个节点释放后双指针同时置空 free(q-front); q-front NULL; q-rear NULL; } q-size--; } // 获取队头元素 QDataType QueueFront(Queue* q) { assert(q q-front); return q-front-data; } // 获取队尾元素 QDataType QueueBack(Queue* q) { assert(q q-rear); return q-rear-data; } // 获取有效元素个数 int QueueSize(Queue* q) { assert(q); return q-size; } // 判空空返回1非空返回0 int QueueEmpty(Queue* q) { assert(q); return q-size 0 ? 1 : 0; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); while (q-front) { QueueNode* node q-front; q-front q-front-next; free(node); } // 释放完节点重置所有状态 q-rear NULL; q-size 0; }5.3 两个核心边界处理链式队列的逻辑难点不在常规操作而在两个边界状态首次入队空队列插入第一个节点时该节点既是队头也是队尾必须同时给front和rear赋值。删除最后一个节点当front rear时释放节点后必须将双指针同时置空否则rear会变成野指针。六、实现踩坑复盘以下是手写过程中真实遇到的典型问题大多不属于「算法不会」而是指针状态维护不完整。序号问题描述后果修正方案1初始化重复赋值front漏写rearrear为随机脏值首次入队访问野内存双指针必须同步初始化为 NULL2malloc后先访问节点成员再判空申请失败时直接对空指针解引用程序崩溃先判空确认成功后再使用节点3新节点未显式置next NULL尾节点next为垃圾值遍历/销毁时越界每个新节点创建后必须手动置空 next4删除最后一个节点只置空frontrear成为野指针指向已释放内存尾节点删除后front、rear 同时置 NULL5销毁队列只释放节点不重置状态销毁后rear野指针、size残留旧值销毁后手动重置 rear 与 size恢复空队列状态6局部临时指针 free 后置 NULL冗余代码无实际作用局部变量函数结束即销毁仅结构体成员指针 free 后需要置空七、测试验证7.1 测试代码 test.c覆盖空队列、多次入出队、清空后重入队等全边界场景#include Queue.h #include stdio.h void PrintQueue(Queue* q) { if (QueueEmpty(q)) { printf(队列[空]\n); return; } QueueNode* cur q-front; printf(队列); while (cur ! NULL) { printf(%d , cur-data); cur cur-next; } printf( | 头%d 尾%d size%d\n, QueueFront(q), QueueBack(q), QueueSize(q)); } int main(void) { Queue q; QueueInit(q); printf(初始化完成\n); PrintQueue(q); printf(\n入队 10,20,30,40\n); QueuePush(q, 10); QueuePush(q, 20); QueuePush(q, 30); QueuePush(q, 40); PrintQueue(q); printf(\n出队两次\n); QueuePop(q); PrintQueue(q); QueuePop(q); PrintQueue(q); printf(\n入队 50,60\n); QueuePush(q, 50); QueuePush(q, 60); PrintQueue(q); printf(\n全部出队直到空\n); while (!QueueEmpty(q)) { QueuePop(q); PrintQueue(q); } printf(\n空队列重新入队 77\n); QueuePush(q, 77); PrintQueue(q); QueueDestroy(q); printf(\n队列销毁完毕\n); return 0; }7.2 运行结果八、复杂度分析操作时间复杂度QueuePush入队O(1)QueuePop出队O(1)QueueFront取队头O(1)QueueBack取队尾O(1)QueueSize求长度O(1)QueueEmpty判空O(1)QueueDestroy销毁O(N)销毁操作必须遍历释放所有节点时间复杂度最低为 O(N)。九、拓展去掉 size 后的变化如果移除size成员结构体变为typedef struct Queue { QueueNode* front; QueueNode* rear; } Queue;产生的影响QueueEmpty 不受影响仍可通过front NULL判空保持 O(1)QueueSize 性能下降必须从头遍历链表计数时间复杂度退化为 O(N)入队出队代码简化无需维护 size 的加减操作简单说size最大的价值就是把「求长度」从线性遍历变成了常数时间。写在最后从顺序栈到链式队列核心都是「操作受限的线性表」但实现思路差异显著顺序栈靠「数组 top 下标」发挥尾插尾删的优势链式队列靠「单链表 双指针 size」适配头删尾插的特性比起死记代码更值得沉淀的是三点数据结构选型要匹配操作场景没有绝对最优只有最合适链式结构最容易出错的永远是边界0个节点、1个节点写数据结构本质是维护「不变量」每一次操作后结构的状态规则必须始终成立Gitee 仓库地址数据结构/8.17 队列练习Queue · Luminous/Code_2026 - 码云 - 开源中国