目录
1.队列的概念和结构
概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先
进先出FIFO(First In First Out)。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列底层结构选型:
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出
队列在数组头上出数据，效率会比较低。
2.队列的实现
关于队列的实现，也是三个文件，头文件，实现文件和测试文件。
2.1 头文件---Queue.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
//队列结点的结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue {
QueueNode* phead;
QueueNode* ptail;
//int size; //队列中有效数据个数
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队--对尾
void QueuePush(Queue* pq, QDataType x);
//出队--对头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素的个数
int QueueSize(Queue* pq);
//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);以下从头文件作用、各部分代码功能、设计逻辑与场 三个维度，拆解这个队列头文件：
一、头文件整体作用
#pragma once 是编译器指令（类似 #ifndef 头文件保护），确保头文件 只被编译一次，避免重
复包含导致的符号冲突。
通过包含标准库头文件（ stdio.h 等）、自定义结构体与函数声明，为队列操作提供 统一接口规
范，让其他 .c 源文件能复用队列功能，实现 “声明与实现分离”，方便代码维护与工程化开发。
二、核心代码逐段解析
1. 标准库依赖
#include<stdio.h> // 提供输入输出（如调试打印）
#include<assert.h> // 提供 assert 断言，用于参数合法性检查
#include<stdlib.h> // 提供内存分配（malloc、free 等）、退出函数（exit）
#include<stdbool.h> // 提供 bool 类型（C99+ 标准），让代码语义更清晰- 作用：为队列操作提供基础工具（内存管理、断言检查、布尔类型），是实现队列的 “底层支
撑”。
2. 队列结点结构（ QueueNode ）
typedef struct QueueNode
{
QDataType data; // 存储队列的实际数据（类型由 QDataType 决定，这里是 int）
struct QueueNode* next; // 指向下一个结点的指针，构建链表结构
}QueueNode;- 设计逻辑：用 链表结点 实现队列，每个结点存数据 + 指向下一结点的指针。
- 优势：链表结构让队列 插入/删除更灵活（无需像数组那样考虑扩容、移位），适合频繁增删的
场景。
3. 队列控制结构（ Queue ）
typedef struct Queue {
QueueNode* phead; // 指向队列的 “队头结点”，出队操作从这里开始
QueueNode* ptail; // 指向队列的 “队尾结点”，入队操作在这里追加
// int size; // （可选）记录队列元素个数，快速获取队列长度
}Queue;- 核心作用：用两个指针 “锚定” 队列的 头尾边界，让入队、出队操作能直接定位头尾，无需遍历
链表，提升操作效率。
- 扩展思考：size 字段可快速返回队列长度（替代遍历计数），适合需要频繁获取队列长度的场
景。
4. 队列操作接口
围绕队列的 初始化、销毁、增删查改 设计，是队列功能的 “对外入口”：
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队--对尾
void QueuePush(Queue* pq, QDataType x);
//出队--对头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素的个数
int QueueSize(Queue* pq);
//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);这些具体函数的功能我们在后面的实现文件中详细介绍。
5. 设计逻辑与应用场景
1. 设计亮点
- 链表实现：规避数组队列的 “假溢出”（数组头空但无法插入）问题，动态分配内存更灵活。
- 头尾双指针：入队、出队操作的时间复杂度都是 O(1)（无需遍历），效率高。
- 接口化封装：将队列操作抽象为函数，调用者无需关心内部实现（黑盒化），降低使用成本。
2. 典型应用场景
- 任务调度：如操作系统的 “任务队列”，按顺序处理用户请求（先到先执行）。
- 消息队列：网络通信中缓存数据包（如 TCP 接收队列），保证数据有序处理。
- 广度优先搜索(BFS):算法中用队列存储待访问节点，按层遍历数据结构（如二叉树层序遍历 ）。
简单来说，这份头文件用 链表 + 头尾指针 的方式，封装了队列的核心操作，让队列能高效实现
“先进先出”，是数据结构中 解耦逻辑、复用代码 的典型实践，也契合工程开发中 “低耦合、高内
聚” 的设计思想。
2.2 实现文件---Queue.c
以下逐一对队列实现代码里的函数，从功能逻辑、时间复杂度、空间复杂度 展开详细分析，帮大
家彻底吃透链表队列的实现：
1. 初始化队列函数--QueueInit函数
void QueueInit(Queue* pq) { assert(pq); // 确保传入的队列指针非空（避免空指针操作） pq->phead = pq->ptail = NULL; // 初始化队头和队尾都指向空（空队列） // pq->size = 0; // 若使用size，初始化为0 }- 功能：把队列的 phead （队头指针）和 ptail （队尾指针）置为 NULL ，初始化队列状
态（若有 size 也会清零）。
- 时间复杂度：O(1)
直接赋值操作，和队列长度无关，执行时间固定。
- 空间复杂度：O(1)
仅操作指针，不额外分配动态内存，空间占用固定。
2. 销毁队列函数--QueueDestroy函数
void QueueDestroy(Queue* pq) { assert(pq); // 确保队列指针非空 QueueNode* pcur = pq->phead; // 从队头开始遍历 while (pcur) // 遍历所有节点，直到pcur为NULL（所有节点都被释放） { QueueNode* next = pcur->next; //先记录下一个节点的地址（避免释放后丢失） free(pcur); // 释放当前节点 pcur = next; // 移动到下一个节点 } pq->phead = pq->ptail = NULL; // 销毁后队头和队尾置空（避免野指针） // pq->size = 0; // 若使用size，重置为0 }- 功能：遍历队列所有结点，逐个 free 释放内存，防止内存泄漏；最后重置头尾指针。
- 时间复杂度：O(n)
n 是队列元素个数，需遍历每个结点释放，遍历次数和 n 成正比。
- 空间复杂度：O(1)
额外只用了 pcur 、 next 两个指针，空间占用不随队列长度变化。
3. 入队函数(队尾插入)--QueuePush函数
void QueuePush(Queue* pq, QDataType x) { assert(pq); // 确保队列指针非空 // 1. 创建新节点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) // 检查内存分配是否成功 { perror("malloc fail"); // 打印错误信息 exit(1); // 退出程序（分配失败无法继续） } // 2. 初始化新节点数据 newnode->data = x; // 存储数据x newnode->next = NULL; // 新节点作为队尾，next置空 // 3. 插入队列 if (pq->phead == NULL) // 若队列为空（头指针为空） { pq->phead = pq->ptail = newnode; // 头和尾都指向新节点 } else // 队列非空 { pq->ptail->next = newnode; // 原队尾节点的next指向新节点 pq->ptail = pq->ptail->next; // 队尾指针移动到新节点（等价于pq->ptail = newnode） } // pq->size++; // 若使用size，计数+1 }- 功能：
1. 动态分配新结点，存数据 x ， next 置空；
2. 若队列为空（ phead == NULL ），头尾指针都指向新结点；
3. 若队列非空，把新结点接在 ptail 后，更新 ptail 到新结点。
- 时间复杂度：O(1)
不管队列多长，都是 “分配内存 + 指针操作”，执行步骤固定。
- 空间复杂度：O(1)（单次操作）
每次入队只分配 1 个结点 的内存，空间与队列长度无关（但整体队列空间是 O(n)，这里算“单次操作” 的空间）。
4.判空函数--QueueEmpty函数
bool QueueEmpty(Queue* pq) { assert(pq); // 确保队列指针非空 return pq->phead == NULL; // 头指针为空则队列为空（返回true），否则非空（返回false） }- 功能：通过 phead == NULL 判断队列有无元素，为空返回 true ，否则 false 。
- 时间复杂度：O(1)
直接判断指针，执行时间固定。
- 空间复杂度：O(1)
无额外动态内存分配，空间占用固定。
5. 出队函数(队头函数)--QueuePop函数
void QueuePop(Queue* pq) { assert(!QueueEmpty(pq)); // 确保队列非空（禁止对空队列执行出队） // 情况1：队列只有一个节点（头和尾指向同一个节点） if (pq->phead == pq->ptail) { free(pq->phead); // 释放唯一节点 pq->phead = pq->ptail = NULL; // 头和尾都置空（避免野指针） } else // 情况2：队列有多个节点 { QueueNode* next = pq->phead->next; // 记录头节点的下一个节点 free(pq->phead); // 释放头节点 pq->phead = next; // 头指针移动到下一个节点 } // pq->size--; // 若使用size，计数-1 }- 功能：
1. 断言队列非空（空队列不能出队）；
2. 若只有 1 个结点，释放后重置头尾为 NULL ；
3. 若多个结点，保存 phead->next ，释放 phead ，再让 phead 指向下一结点。
- 时间复杂度：O(1)
不管队列多长，都是 “指针操作 + 释放 1 个结点”，步骤固定。- 空间复杂度：O(1)
额外只用 next 指针，空间占用固定。
6. 取队头数据函数--QueueFront函数
QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); // 确保队列非空（空队列无数据） return pq->phead->data; // 返回头节点的数据 }- 功能：断言队列非空后，返回 phead 结点的数据。
- 时间复杂度：O(1)
直接访问 phead->data ，执行时间固定。
- 空间复杂度：O(1)
无额外动态内存，空间占用固定。
7. 取队尾数据函数--QueueBack函数
QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); // 确保队列非空 return pq->ptail->data; // 返回尾节点的数据 }- 功能：断言队列非空后，返回 ptail 结点的数据。
- 时间复杂度：O(1)
直接访问 ptail->data ，执行时间固定。
- 空间复杂度：O(1)
无额外动态内存，空间占用固定。
8. 统计队列元素个数函数--QueueSize函数
int QueueSize(Queue* pq) { assert(pq); // 确保队列指针非空 // 遍历计数：从队头开始，逐个移动指针并计数 QueueNode* pcur = pq->phead; int size = 0; while (pcur) // 遍历所有节点 { size++; // 计数+1 pcur = pcur->next; // 移动到下一个节点 } return size; // 返回总个数 //第二种方式: 遍历列表---适用于频繁调用队列有效数据个数的场景 //return size; }- 功能：遍历队列，统计结点总数（从 phead 遍历到 NULL ，计数 size ）。
- 时间复杂度：O(n)
n 是队列元素个数，需逐个遍历计数，遍历次数和 n 成正比。
- 空间复杂度：O(1)
额外只用 pcur 指针和 size 变量，空间占用固定。第二种统计队列元素个数的方式很简单：
在队列结构体里加一个 int size 变量，专门记录元素个数。
- 初始化队列时， size = 0 ；- 入队（Push）时， size++ ；
- 出队（Pop）时， size-- ；
- 统计个数（QueueSize）时，直接返回 size 。
对比两种方式：
- 遍历计数：不用额外变量，但每次统计都要从头走到尾，慢（适合不常统计的场景）。
- size变量：多占一点点内存，但统计时直接拿结果，快（适合经常要知道队列长度的场景）。最主要的是时间复杂度是O（1），对比第一种方法的时间复杂度更加高效。两种方法
的具体选择要根据不同的场景，如果队列长度不经常统计的话，选择第一种方式也就是遍历
计数, 如果要经常知道队列的长度, 应选择第二种size变量的方式, 减小时间复杂度,提高效
率。
9. 总结
这种 链表实现的队列，优势在于入队、出队（除销毁和统计长度外）都是 O(1) 高效操作，适合频
繁增删的场景。
2.3 测试文件---test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
//QueuePop(&q);
int front = QueueFront(&q);
int rear = QueueBack(&q);
printf("front:%d\n", front);
printf("rear:%d\n", rear);
printf("size:%d\n", QueueSize(&q));
QueueDestroy(&q);
}
int main()
{
test01();
return 0;
}以下从 代码功能拆解、文件角色分工、模块协作关系 三个维度，详细解析这份队列代码的实现逻
辑，帮你理清它们的关联：
一、代码功能逐段拆解（ test.c 文件）
1. 头文件与函数声明
#include"Queue.h"- 作用：
- #include"Queue.h" ：引入队列的 接口声明（结构体、函数原型），让 test.c 能调用队列
操作函数。
2. test01测试函数
void test01() { // 1. 定义队列变量 Queue q; // 2. 初始化队列 QueueInit(&q); // 3. 入队操作（队尾追加数据） QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); // 4. （注释的出队）QueuePop(&q); // 5. 获取队头、队尾数据 int front = QueueFront(&q); int rear = QueueBack(&q); // 6. 打印数据 printf("front:%d\n", front); // 输出队头（1） printf("rear:%d\n", rear); // 输出队尾（3） printf("size:%d\n", QueueSize(&q)); // 输出队列长度（3） // 7. 销毁队列（释放内存） QueueDestroy(&q); }- 功能流程：
「定义队列 → 初始化 → 入队 →（可选出队）→ 获取头尾数据 → 打印 → 销毁」，完整覆盖队列的 常用操作链路。
- 关键细节：
- 队列是 结构体变量 q ，通过指针 &q 传递给函数（因为函数要修改队列的phead 、 ptail 等内部状态）。
- 注释的 QueuePop(&q); 若取消注释，队头元素（1）会被移除，后续 front 会变成2 ， size 变成 2 。
3. main函数
int main() { test01(); // 调用测试函数 return 0; }- 作用：程序入口，执行 test01 测试逻辑，验证队列功能是否正常。
3. 总结
以上面是关于三个文件的全部解释内容。下面小编把完整版的代码奉上:
1. 头文件---Queue.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
//队列结点的结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue {
QueueNode* phead;
QueueNode* ptail;
//int size; //队列中有效数据个数
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队--对尾
void QueuePush(Queue* pq, QDataType x);
//出队--对头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素的个数
int QueueSize(Queue* pq);
//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);2. 实现文件---Queue.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
//pq->size = 0;
}
//销毁对列
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
//pq->size = 0;
}
//入队--对尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else//队列非空
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next; //pq->ptail = newnode;
}
//pq->size++;
}
//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
//出队--队头
void QueuePop(Queue* pq)
{
assert(!QueueEmpty(pq));
//只有一个节点,phead和ptail都置为空(先释放后指控)
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
//pq->size--;
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
//第一种方式: 遍历列表---适用于不会频繁调用队列有效数据个数的场景
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
size++;
pcur = pcur->next;
}
return size;
//第二种方式: 遍历列表---适用于频繁调用队列有效数据个数的场景
//return size;
}3. 测试文件---test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
//QueuePop(&q);
int front = QueueFront(&q);
int rear = QueueBack(&q);
printf("front:%d\n", front);
printf("rear:%d\n", rear);
printf("size:%d\n", QueueSize(&q));
QueueDestroy(&q);
}
int main()
{
test01();
return 0;
}4.文件角色与分工
文件 角色定位 核心内容 类比现实场景
- Queue.h 接口层（“使用说明书”） 队列结构体、函数原型声明
- Queue.c 实现层（“具体功能代码”） 队列函数的实际逻辑（怎么初始化、入队等）
- test.c 测试层（“功能验证”） 调用队列接口，测试功能是否正常
- 编译时： Queue.c 和 test.c 会分别编译成目标文件（如 Queue.o 、 test.o ），各自包含自己
的代码逻辑。
- 链接时：编译器会把 Queue.c 中函数的实现，和 test.c 中函数的调用 “对接”，确保 test.c 调
用的 QueuePush 能找到 Queue.c 里的实际代码。
总结（一句话梳理关系）:
Queue.h 定义 “队列怎么用”， Queue.c 实现 “队列怎么做”， test.c 通过 #include"Queue.h" 拿
到 “用法”，调用 Queue.c 的 “实现” 来测试队列功能。三者通过 接口声明 + 实现分离 的方式，让
代码可复用、易维护，是 C 语言工程化开发的典型实践。这样的文件模式和我们之前学习的种种
数据结构的文件模式都一样。
以上便是是关于队列的所有内容。感谢大家的观看！