=========================================================================
相关代码gitee自取：
C语言学习日记: 加油努力 (gitee.com)
=========================================================================
接上期：
【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）_高高的胖子的博客-CSDN博客
=========================================================================
1 . 队列（Queue）
队列的概念和结构：
队列的概念
- 队列是一种只允许在一端执行插入数据操作，在另一端进行删除数据操作的特殊线性表
- 入队列 -- 进行插入操作的一端称为队尾
出队列 -- 进行删除操作的一端称为队头
- 队列中的数据元素遵守
先进先出（FIFO -- First In First Out）的原则 -- 先进入的元素会先出来
所以可以应用在公平性排队(抽号机)、BFS(广度优先遍历)
队列的结构
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2 . 队列的实现
使用 顺序表(数组) 或 链表(链式结构) 都可以实现队列，
使用顺序表的话，入队列比较简单，但在出队列时需要删除和挪动数据，效率较低，
所以下面用链表(链式结构)实现队列 -- 单向 + 无头 + 非循环 链表
入队 -- 单链表尾部插入(尾插) ； 出队 -- 单链表头部删除(头删)
（详细解释在图片的注释中，代码分文件放下一标题处）
实现具体功能前的准备工作
- 定义队列(链式结构)中数据域存储的数据类型
- 定义队列(链式结构)结点类型
包含 队列指针域 和 队列数据域
- 定义队列类型
包含 头结点指针 、尾结点指针 和 队列结点(元素)个数图示
---------------------------------------------------------------------------------------------文章来源：https://www.toymoban.com/news/detail-712990.html
QueueInit函数 -- 将队列进行初始化
- assert断言队列类型指针不为空
- 将队头结点置为空
将队尾结点置为空
队列结点(元素)个数置为0图示
---------------------------------------------------------------------------------------------
QueueDestroy函数 -- 将队列销毁
- assert断言队列类型指针不为空
- 创建一个在队列进行遍历的指针cur
使用while循环进行遍历释放队列结点
- 结点都释放后，把队头队尾指针都置空
- 再把队列结点(元素)个数置为0
图示
---------------------------------------------------------------------------------------------
QueuePush函数 -- 用链表的尾插操作实现入队
- assert断言队列类型指针不为空
- 为队列结点开辟动态空间并检查空间开辟情况
- 结点开辟成功后
将尾插值(x)赋给队列结点的数据域并将指针域置为空
- 空间开辟后进行尾插
如果队列刚初始化队列为空，将刚开辟的结点newnode地址赋给头尾结点指针
队列不为空，正常进行尾插操作
- 插入数据后队列结点(元素)个数++
图示
---------------------------------------------------------------------------------------------
QueuePop函数 -- 用链表的头删操作实现出队
- assert断言队列类型指针不为空和队列不为空
- 出队(头删)分两种情况：
队列中只剩一个结点 -- 头删后头指针移动，尾指针也要移动
队列不止一个结点 -- 头删后只需移动队头结点
- “删除”后队列结点(元素)个数--
图示
---------------------------------------------------------------------------------------------
QueueFront函数 -- 返回队头结点的数据域数据
- assert断言队列类型指针不为空和队列不为空
- 队列有数据，则直接返回队头结点数据域数据
图示
---------------------------------------------------------------------------------------------
QueueBack函数 -- 返回队尾结点的数据域数据
- assert断言队列类型指针不为空和队列不为空
- 队列有数据，则直接返回队尾结点数据域数据
图示
---------------------------------------------------------------------------------------------
QueueEmpty函数 -- 判断队列是否为空
- assert断言队列类型指针不为空
- 直接判断队头结点指向的下个结点是否为空，直接返回判断结果
图示
---------------------------------------------------------------------------------------------
QueueSize函数 -- 判断队列结点(元素)个数
- assert断言队列类型指针不为空
- 直接返回size队列结点(元素)个数
图示
---------------------------------------------------------------------------------------------
总体测试：
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3 . 对应代码
Queue.h -- 队列头文件
#pragma once //包含之后需要的头文件： #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //以链表（链式结构）实现队列： //双向+循环 的链表可以解决找尾结点的问题， //定义一个尾指针也可以解决该问题， //哨兵位 可以解决二级指针的问题， //且尾插时可以少一层判断，但还有方法可以解决 //定义队列(链式结构)中数据域存储的数据类型： typedef int QDataType; //定义队列(链式结构)结点类型： typedef struct QueueNode { //队列指针域： struct QueueNode* next; //队列数据域： QDataType data; }QNode; //将类型重命名为Qnode //定义队列类型： typedef struct Queue { //因为用链表尾插实现入队， //用链表头删实现出队， //那么就需要头结点和尾结点的指针， //所以可以直接将这两个指针封装为一个类型， //队列类型： //头结点指针： QNode* head; //尾结点指针： QNode* tail; //记录队列结点(元素)个数： int size; //这样之后在出队和入队操作时， //就不需要用到二级指针， //直接接收这个结构体指针， //通过结构体指针运用结构体里的头尾结点指针， //再用头尾结点指针定义头尾结点 //来实现 二级指针、带哨兵位头结点 和 返回值 的作用 //所以现在已知的通过指针定义结点的方法就有4种： // 1. 结构体包含结点指针 // 2. 二级指针调用结点指针 // 3. 哨兵位头结点指针域next指向结点地址 // 4. 返回值返回改变的结点指针 }Que; //重命名为Que //队列初始化函数 -- 将队列进行初始化 //接收队列类型指针(包含链表头尾结点) void QueueInit(Que* pq); //队列销毁函数 -- 将队列销毁 //接收队列类型指针(包含链表头尾结点) void QueueDestroy(Que* pq); //队列入队函数 -- 用链表的尾插操作实现入队 //接收队列类型指针(包含链表头尾结点) 、尾插值 void QueuePush(Que* pq, QDataType x); //队列出队函数 -- 用链表的头删操作实现出队 //接收队列类型指针(包含链表头尾结点) void QueuePop(Que* pq); //队头函数 -- 返回队头结点的数据域数据 //接收队列类型指针(包含链表头尾结点) QDataType QueueFront(Que* pq); //队尾函数 -- 返回队尾结点的数据域数据 //接收队列类型指针(包含链表头尾结点) QDataType QueueBack(Que* pq); //判空函数 -- 判断队列是否为空 //接收队列类型指针(包含链表头尾结点) bool QueueEmpty(Que* pq); //队列大小函数 -- 判断队列结点(元素)个数 //接收队列类型指针(包含链表头尾结点) int QueueSize(Que* pq);
---------------------------------------------------------------------------------------------
文章来源地址https://www.toymoban.com/news/detail-712990.html
Queue.c -- 队列函数实现文件
#define _CRT_SECURE_NO_WARNINGS 1 //包含队列头文件： #include "Queue.h" //队列初始化函数 -- 将队列进行初始化 //接收队列类型指针(包含链表头尾结点) void QueueInit(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //将队头结点置为空： pq->head = NULL; //将队尾结点置为空： pq->tail = NULL; //队列结点(元素)个数置为0： pq->size = 0; } //队列销毁函数 -- 将队列销毁 //接收队列类型指针(包含链表头尾结点) void QueueDestroy(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //释放队列跟单链表的释放一样 //先创建一个在队列进行遍历的指针： QNode* cur = pq->head; //从队头结点开始 //使用while循环进行遍历释放队列结点： while (cur != NULL) { //先保存下个结点： QNode* next = cur->next; //再释放当前结点： free(cur); //再指向下个结点： cur = next; } //结点都释放后，把队头队尾指针都置空： pq->head = NULL; pq->tail = NULL; //再把队列结点(元素)个数置为0： pq->size = 0; } //队列入队函数 -- 用链表的尾插操作实现入队 //接收队列类型指针(包含链表头尾结点) 、尾插值 void QueuePush(Que* pq, QDataType x) { //assert断言队列类型指针不为空： assert(pq != NULL); //入队放入元素需要空间， //所以要先为队列结点开辟动态空间： QNode* newnode = (QNode*)malloc(sizeof(QNode)); //检查是否开辟成功： if (newnode == NULL) { //开辟失败则打印错误信息： perror("malloc fail"); //终止程序： exit(-1); } //队列结点完成后将尾插值(x) //赋给队列结点数据域： newnode->data = x; //指针域指向空： newnode->next = NULL; //空间开辟后进行尾插： if (pq->tail == NULL) //如果队列刚初始化，队列为空， //头结点指针和尾结点指针都为空： { //那么将刚开辟的结点newnode地址 //赋给头结点指针和尾结点指针 pq->head = newnode; pq->tail = newnode; } else //队列不为空，进行尾插： { //将目前队尾结点指针域next指向尾插结点： pq->tail->next = newnode; //然后再指向尾插结点，成为新队尾结点： pq->tail = newnode; } //插入数据后队列结点(元素)个数++： pq->size++; } //队列出队函数 -- 用链表的头删操作实现出队 //接收队列类型指针(包含链表头尾结点) void QueuePop(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //assert断言队列不为空，没数据不能删除： assert(QueueEmpty(pq) != true); //不为空就继续程序 //如果队列中只剩一个结点： if (pq->head->next == NULL) //队头指针指向空，说明只剩一个结点， //只剩一个结点说明队头队尾指针都指向这一个结点， //所以这时头删后头指针移动，尾指针也要移动 { //先释放("删除")队列目前头结点： free(pq->head); //删除后将队头队尾指针都置为空： pq->head = NULL; pq->tail = NULL; } else //队列不止一个结点，则头删后只需移动队头结点： { //用链表的头删操作实现出队, //先保存第二个结点地址： QNode* next = pq->head->next; //释放("删除")队列目前头结点： free(pq->head); //再将队头结点指针指向原本第二个结点next， //让其成为新的队头结点： pq->head = next; } //“删除”后队列结点(元素)个数--： pq->size--; } //队头函数 -- 返回队头结点的数据域数据 //接收队列类型指针(包含链表头尾结点) QDataType QueueFront(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //assert断言队列不为空，没数据不能查找： assert(QueueEmpty(pq) != true); //不为空就继续程序 //队列有数据，则直接返回队头结点数据域数据： return pq->head->data; } //队尾函数 -- 返回队尾结点的数据域数据 //接收队列类型指针(包含链表头尾结点) QDataType QueueBack(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //assert断言队列不为空，没数据不能查找： assert(QueueEmpty(pq) != true); //不为空就继续程序 //队列有数据，则直接返回队尾结点数据域数据： return pq->tail->data; } //判空函数 -- 判断队列是否为空 //接收队列类型指针(包含链表头尾结点) bool QueueEmpty(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //直接判断队头结点指向的下个结点是否为空： return pq->head == NULL; //是则返回true -- 队列为空 //是则返回false -- 队列不为空 } //队列大小函数 -- 判断队列结点(元素)个数 //接收队列类型指针(包含链表头尾结点) int QueueSize(Que* pq) { //assert断言队列类型指针不为空： assert(pq != NULL); //直接返回size队列结点(元素)个数： return pq->size; }
---------------------------------------------------------------------------------------------
Test.c -- 队列测试文件
#define _CRT_SECURE_NO_WARNINGS 1 //包含队列头文件： #include "Queue.h" //队列测试函数： void TestQueue() { //创建队列类型： Que q; //对队列类型进行初始化： QueueInit(&q); //进行入队操作： QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); //当前队尾值： printf("当前队尾值：%d\n", QueueBack(&q)); //当前队列元素个数： printf("当前队列元素个数：%d\n", QueueSize(&q)); //换行： printf("\n"); //使用while循环遍历进行出队： //（类似抽号机，当前号抽完就到下个号） while (!QueueEmpty(&q)) //队列不为空就继续出队： { //打印出队值： printf("当前出队值为：%d\n", QueueFront(&q)); //进行出队： QueuePop(&q); //出队后打印下个出队值 } //换行： printf("\n"); //当前队列元素个数： printf("当前队列元素个数：%d", QueueSize(&q)); //销毁队列： QueueDestroy(&q); } //主函数： int main() { //调用队列测试函数： TestQueue(); return 0; }
到了这里，关于【数据结构初阶】六、线性表中的队列（C语言 -- 链式结构实现队列）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
