前言队列Queue是我们日常生活中再熟悉不过的概念——排队买奶茶、银行叫号、打印机任务调度背后都是队列的思想。在计算机世界队列更是操作系统进程调度、消息队列、BFS 算法的基石。本文会从零开始手写一个完整的链式队列C语言实现并逐段拆解代码的设计思路让你不仅会用更懂为什么这么写。如果你正在学数据结构或者准备面试这篇文章值得你花 15 分钟认真读完。一、什么是队列——先进先出FIFO1.1概念队列只允许在一端进行数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出的规则。我们不难发现队列的逻辑结构是线性的但是物理结构不一定是线性的。入队列进行插入操作的一端称为队尾。出队列进行删除操作的一端称为队头1.2为什么用链表实现队列队列有两种常见实现方式实现方式入队出队数组顺序队列O(1)O(n)(需移动元素链表链式队列O(1)O(1)如果用数组的话出队时头元素删除后后面的元素要整体前移效率低下。而链表只需改变指针时间复杂度O1所以实际工程中链式队列更常用。二、队列的接口设计(Queue.h中进行声明)在执行操作之前我们依然是需要先创建三个文件分别是Queue.h、Queue.c、test.c。三、结构体定义1.每个节点是独立的堆内存通过 next 指针串联起来不需要连续空间支持动态扩容2.用 typedef 重命名数据类型后续想存char、结构体都能一键修改复用性强为什么需要单独定义一个Queue结构体因为队列需要同时维护头和尾两个指针把它们封装在一起函数传参更清晰也更方便管理。如果只用一个头指针每次入队都要遍历到尾时间复杂度编程O(n)失去了链表的优势。四、代码逐段精讲Queue.c中实现4.1初始化——QueueInit1.assert(pq) 防御式编程防止外面传NULL空指针进来导致后续 pq-phead 非法访问崩溃2.把头尾指针都置为 NULL 代表当前队列为空没有任何节点3.初始化只操作指针不创建节点节点只有在入队时才动态开辟4.2判空——QueueEmpty1.空队列的标志就是 phead NULL 直接返回表达式结果即可代码最简洁2.返回值用 bool 类型语义清晰后续出队、取数据的断言都可以直接复用这个函数4.3入队——队尾插入QueuePush1.先创建节点再接入 malloc 开辟内存后必须检查是否失败内存不足时 malloc 会返回NULL不判断会造成野指针崩溃。2.新节点 next 必须手动置空 malloc 出来的内存是随机垃圾值不置空的话后续遍历会越界。3.为什么要分空队列和非空队列1空队列时头尾指针都指向NULL新节点是第一个节点必须同时给 phead 和 ptail 赋值2非空队列时只需要操作尾指针头指针保持不动4. 两步操作不能反必须先把新节点接在原尾节点后面再移动尾指针否则原尾节点地址会丢失链表就断了。4.4出队——队头删除QueuePop1. assert(!QueueEmpty(pq)) 空队列不能出队属于非法操作直接断言拦截2. 为什么要单独处理「只剩一个节点」的情况当队列只有一个节点时 phead 和 ptail 指向同一个节点。如果只释放 phead 、只移动 phead ptail 就会变成悬空指针野指针指向已经被释放的内存后续入队会崩溃。所以这种情况必须同时把两个指针都置空。3. 多个节点的场景先保存下一个节点地址再释放头节点最后头指针后移。顺序不能乱否则free后头节点没了就找不到下一个节点了。4.5取队头数据——QueueFront1. 只读操作不修改队列结构直接返回头节点的 data 即可2. 必须断言非空空队列没有数据访问 phead-data 属于空指针解引用直接崩溃4.6取队尾数据——QueueBack1. 只读操作不修改队列结构直接返回尾节点的 data 即可2. 必须断言非空空队列没有数据访问 ptail-data 属于空指针解引用直接崩溃4.7取队列有效元素个数——QueueSize1. 同样用临时指针遍历计数不改动原队列2. 时间复杂度O(N)需要遍历整条链表3. 拓展优化如果想O(1)获取长度可以在 Queue 结构体里加一个 size 成员入队1、出队-1用一点点空间换时间。如下图这样修改即可4.8打印队列——QueuePrint1. 先判空空队列直接提示并返回避免无效遍历2. 绝对不能直接移动 phead 遍历如果让 phead 自己往后走遍历完头指针就丢了整个队列都找不到了。所以用临时指针 pcur 拷贝头节点地址只动临时变量原队列结构丝毫不改。3. 终止条件 pcur NULL 代表已经遍历完最后一个节点4.9销毁队列——QueueDestory1. 为什么要先保存 next 再free节点被free之后它的内存就被回收了再去访问 pcur-next 是非法的。所以必须在释放当前节点前先把下一个节点的地址存下来。2. 遍历释放完所有节点后一定要把头尾指针置空避免变成野指针并把size归零3. 销毁只释放链表节点队列结构体本身是外面定义的不需要我们free五、可执行代码验证test.c中实现六、总结1. 链式队列核心是单链表 头尾双指针保证入队、出队都是O(1)时间复杂度2. 所有只读操作打印、计数都要用临时指针遍历绝对不能改动原头尾指针3. 边界场景一定要单独处理空队列入队、只剩一个节点出队是最容易出野指针的地方4. 动态开辟的节点一定要记得销毁防止内存泄漏