数据结构 队列

目录

1.队列的概念和结构

2.队列的实现

2.1 头文件---Queue.h

1. 标准库依赖

2. 队列结点结构（ QueueNode ）

3. 队列控制结构（ Queue ）

 4. 队列操作接口

5. 设计逻辑与应用场景

2.2 实现文件---Queue.c

1. 初始化队列函数--QueueInit函数

2. 销毁队列函数--QueueDestroy函数

3. 入队函数(队尾插入)--QueuePush函数 

4.判空函数--QueueEmpty函数

5. 出队函数(队头函数)--QueuePop函数

6. 取队头数据函数--QueueFront函数

7. 取队尾数据函数--QueueBack函数

8. 统计队列元素个数函数--QueueSize函数

9. 总结

2.3 测试文件---test.c

1. 头文件与函数声明

2.  test01测试函数

3.  main函数

3. 总结

1. 头文件---Queue.h

2. 实现文件---Queue.c

3. 测试文件---test.c

4.文件角色与分工

---

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;  // 存储数据xnewnode->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++;  // 计数+1pcur = 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 语言工程化开发的典型实践。这样的文件模式和我们之前学习的种种

数据结构的文件模式都一样。

以上便是是关于队列的所有内容。感谢大家的观看！