前言

队列（Queue）是我们日常生活中再熟悉不过的概念——排队买奶茶、银行叫号、打印机任务调度，背后都是队列的思想。在计算机世界，队列更是操作系统进程调度、消息队列、BFS 算法的基石。

本文会从零开始，手写一个完整的链式队列（C语言实现），并逐段拆解代码的设计思路，让你不仅会用，更懂为什么这么写。

如果你正在学数据结构，或者准备面试，这篇文章值得你花 15 分钟认真读完。

一、什么是队列？——先进先出（FIFO）

1.1概念

队列只允许在一端进行数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的规则。我们不难发现，队列的逻辑结构是线性的但是物理结构不一定是线性的。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头

1.2为什么用链表实现队列？

队列有两种常见实现方式：

如果用数组的话，出队时头元素删除后，后面的元素要整体前移，效率低下。而链表只需改变指针，时间复杂度O（1），所以实际工程中链式队列更常用。

二、队列的接口设计(Queue.h中进行声明)

在执行操作之前，我们依然是需要先创建三个文件，分别是Queue.h、Queue.c、test.c。

三、结构体定义

1.每个节点是独立的堆内存，通过 next 指针串联起来，不需要连续空间，支持动态扩容

2.用 typedef 重命名数据类型，后续想存char、结构体都能一键修改，复用性强

为什么需要单独定义一个Queue结构体？

因为队列需要同时维护头和尾两个指针，把它们封装在一起，函数传参更清晰，也更方便管理。如果只用一个头指针，每次入队都要遍历到尾，时间复杂度编程O(n)，失去了链表的优势。

四、代码逐段精讲（Queue.c中实现）

4.1初始化——QueueInit

1.assert(pq) ：防御式编程，防止外面传NULL空指针进来，导致后续 pq->phead 非法访问崩溃

2.把头尾指针都置为 NULL ，代表当前队列为空，没有任何节点

3.初始化只操作指针，不创建节点，节点只有在入队时才动态开辟

4.2判空——QueueEmpty

1.空队列的标志就是 phead == NULL ，直接返回表达式结果即可，代码最简洁

2.返回值用 bool 类型，语义清晰，后续出队、取数据的断言都可以直接复用这个函数

4.3入队——队尾插入（QueuePush）

1.先创建节点再接入： malloc 开辟内存后必须检查是否失败，内存不足时 malloc 会返回NULL，不判断会造成野指针崩溃。

2.新节点 next 必须手动置空： malloc 出来的内存是随机垃圾值，不置空的话后续遍历会越界。

3.为什么要分空队列和非空队列？

（1）空队列时，头尾指针都指向NULL，新节点是第一个节点，必须同时给 phead 和 ptail 赋值

（2）非空队列时，只需要操作尾指针，头指针保持不动

4. 两步操作不能反：必须先把新节点接在原尾节点后面，再移动尾指针；否则原尾节点地址会丢失，链表就断了。

4.4出队——队头删除（QueuePop）

1. assert(!QueueEmpty(pq)) ：空队列不能出队，属于非法操作，直接断言拦截

2. 为什么要单独处理「只剩一个节点」的情况？
当队列只有一个节点时， phead 和 ptail 指向同一个节点。
如果只释放 phead 、只移动 phead ， ptail 就会变成悬空指针（野指针），指向已经被释放的内存，后续入队会崩溃。
所以这种情况必须同时把两个指针都置空。

3. 多个节点的场景：先保存下一个节点地址，再释放头节点，最后头指针后移。顺序不能乱，否则free后头节点没了，就找不到下一个节点了。

4.5取队头数据——QueueFront

1. 只读操作，不修改队列结构，直接返回头节点的 data 即可

2. 必须断言非空：空队列没有数据，访问 phead->data 属于空指针解引用，直接崩溃

4.6取队尾数据——QueueBack

1. 只读操作，不修改队列结构，直接返回尾节点的 data 即可

2. 必须断言非空：空队列没有数据，访问 ptail->data 属于空指针解引用，直接崩溃

4.7取队列有效元素个数——QueueSize

1. 同样用临时指针遍历计数，不改动原队列

2. 时间复杂度O(N)，需要遍历整条链表

3. 拓展优化：如果想O(1)获取长度，可以在 Queue 结构体里加一个 size 成员，入队+1、出队-1，用一点点空间换时间。如下图这样修改即可

4.8打印队列——QueuePrint

1. 先判空：空队列直接提示并返回，避免无效遍历

2. 绝对不能直接移动 phead 遍历：如果让 phead 自己往后走，遍历完头指针就丢了，整个队列都找不到了。
所以用临时指针 pcur 拷贝头节点地址，只动临时变量，原队列结构丝毫不改。

3. 终止条件： pcur == NULL ，代表已经遍历完最后一个节点

4.9销毁队列——QueueDestory

1. 为什么要先保存 next 再free？
节点被free之后，它的内存就被回收了，再去访问 pcur->next 是非法的。
所以必须在释放当前节点前，先把下一个节点的地址存下来。

2. 遍历释放完所有节点后，一定要把头尾指针置空，避免变成野指针，并把size归零

3. 销毁只释放链表节点，队列结构体本身是外面定义的，不需要我们free

五、可执行代码验证（test.c中实现）

六、总结

1. 链式队列核心是单链表 + 头尾双指针，保证入队、出队都是O(1)时间复杂度

2. 所有只读操作（打印、计数）都要用临时指针遍历，绝对不能改动原头尾指针

3. 边界场景一定要单独处理：空队列入队、只剩一个节点出队，是最容易出野指针的地方

4. 动态开辟的节点一定要记得销毁，防止内存泄漏