【数据结构】队列——超详解！！！（包含队列的实现）
【数据结构】队列——超详解！！！（包含队列的实现）
前言
往期我们的学习中讲到了顺序表、链表以及栈
它们可以帮我们解决很多问题，而类似的数据结构还有很多
今天，我们就来聊聊——队列
一、队列是什么？
1. 队列的定义
队列：
特殊的线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作的一种数据结构
队列具有先进先出FIFO(First In First Out) 的原则
2. 队尾&&队头
进行插入操作的一端称为队尾
进行删除操作的一端称为队头
3.类比
就像我们在餐厅吃饭时，若饭店满人了，也许就会开始排队摇号，有1号、2号、3号…等等
当有座位空出来时，就让序号前的人先去；当又有人来时，就在队尾加一个序列
而队列也是如此，只允许在一端进行插入数据操作，在另一端进行删除数据操作的一种数据结构
当要删除数据时，就让队头的数据（先来的数据）先删除；当要插入数据时，就在队尾插入数据
二、队列的实现
那么，我们该如何来实现队列呢？
1. 用什么来实现？
想要实现队列，首先要想清楚要用什么实现队列
之前，我们依次实现了顺序表、链表以及栈，他们都是用数组或链表来实现的
队列也可以数组和链表的结构实现
但是之前我们讲到了在数组上头删（出队列）很麻烦，后续的每一个元素都要往前挪一位
如果使用数组的结构来实现队列，出队列就会在数组头上出数据，效率会很低
综上所诉，使用链表的结构来实现队列更优一些
2. 实现思路
由于队列与单链表类似，这里可以拿单链表的实现来做参考
- 第1步
与单链表同理，队列中的每一个节点有以下两成员：
1.指向下一个节点的指针
2.节点中存储的数据
- 第2步
但是，我们需要记录下队列的总元素个数、头节点、尾节点这三个重要信息
于是乎，我们可以单独创建一个结构体来包含这些信息，将队列的总元素个数、头节点、尾节点包含在内
- 第3步
最后，就是一一实现我们队列的增、删、查、改等操作了
3. 代码实现
本文以创建一个 int 类型的队列为例
（1）创建头文件&源文件
之前在讲解扫雷游戏中我就提到:
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱
如图:
创建了一个 “ Queue.h "头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个 “ Queue.c "源文件
用于用来放函数的定义(队列的主体)
还有一个 ” Test.c "源文件
用于测试实现的队列的运行效果
（2）定义队列（定义）
首先我们要定义一个队列
这里之前讲过，要先创建一个结构体来表示每个节点
再单独创建一个结构体来包含这些信息，将队列的总元素个数、头节点、尾节点包含在内
这样方便我们对队列的实现
代码演示：（内有注释）
（在头文件“ Queue.h "中写）
//重定义，方便修改类型typedefint QDataType;//表示每个节点的类型typedefstructQListNode{ QDataType data;//节点中存储的数据structQListNode* next;//指向下一个节点的指针}QNode;// 队列的结构 typedefstructQueue{ QNode* front;//头指针 QNode* tail;//尾指针int size;//总元素个数}Queue;在定义队列的代码中，有两个需要注意的点：本文是以int类型为例，但如果以后要将队列中的元素类型修改成char类型或是其他类型一个一个修改就很麻烦
所以我们重定义int类型为QDataType,并将接下来代码中的int类型全部写成QDataType
这是为了方便我们以后对类型进行修改，仅需将int改为其他类型即可在定义队列的同时重定义队列的变量名为QNode方便以后使用
（3）队列的初始化（初始化）
定义完队列后，肯定要对队列进行初始化，内容全部置 0 / NULL代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 初始化队列 voidQueueInit(Queue* q);在“ Queue.c "源文件中写到：
// 初始化队列 voidQueueInit(Queue* q){assert(q);//断言空指针 q->front =NULL; q->tail =NULL; q->size =0;//全部初始化置 0 / NULL}在写实现代码中，有一个很重要的点：
当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的
故为了我们的代码更加健壮，可以加入assert 断言来判断是否符合条件，在之后的代码中也都有
关于更加详细的assert 断言介绍可参见下文：
【C语言】带你层层深入指针——指针详解3（野指针、assert等）
（4）队列的销毁（销毁）
在我们的程序运行完毕后，当然要对队列进行销毁，以免占用内存
这里我们直接遍历链表，一一释放空间销毁就行啦
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 销毁队列 voidQueueDestroy(Queue* q);在“ Queue.c "源文件中写到：
// 销毁队列 voidQueueDestroy(Queue* q){assert(q);//断言空指针 QNode* cur = q->front;//遍历链表，一一释放空间销毁while(cur){ QNode* next = cur->next;free(cur); cur = next;} q->front = q->tail =NULL; q->size =0;//全部初始化置 0 / NULL}（5）队尾入队列（尾插）
- 怎么插入？
在入队列时，由于队列只允许在一端进行插入数据操作，在另一端进行删除数据
所以我们在插入时进行尾插数据
而在删除时进行头删数据
- 怎么开辟空间？
由于这里是链表的结构，故每一次插入时开辟一个节点的空间就行了
- 注意！！！
注意：当队列中没有节点时
此时插入的节点既是头节点，又是尾节点
所以头尾节点都要赋值
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 队尾入队列 voidQueuePush(Queue* q, QDataType data);在“ Queue.c "源文件中写到：
// 队尾入队列 voidQueuePush(Queue* q, QDataType data){assert(q);//断言空指针 QNode* tmp =(QNode*)malloc(sizeof(QNode));//直接开辟一个节点的空间if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("malloc");return;}//没有问题后就赋值 tmp->data = data; tmp->next =NULL;//注意：当队列中没有节点时//此时插入的节点既是头节点，又是尾节点if(q->size ==0){ q->front = tmp; q->tail = tmp;}else{ q->tail->next = tmp; q->tail = tmp;} q->size++;}（6）队头出队列 （头删）
- 怎么删除？
在出队列时，由于队列只允许在一端进行插入数据操作，在另一端进行删除数据
刚刚我们在队尾进行插入数据
而现在删除数据时就是用头删数据
- 注意！！！
注意：当队列中只有一个节点时
此时头尾节点相等，都要进行删除
所以将头节点和尾节点都释放
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 队头出队列 voidQueuePop(Queue* q);在“ Queue.c "源文件中写到：
// 队头出队列 voidQueuePop(Queue* q){assert(q);assert(q->size >0);//断言空指针//断言顺序表不能为空//注意：当队列中只有一个节点时，头尾节点相等//此时将头节点和为尾节点都释放if(q->size ==1){free(q->front); q->front =NULL; q->tail =NULL;}else{ QNode* del = q->front; q->front = q->front->next;free(del);} q->size--;}（7）获取队列头部元素
这个很简单，直接用下标进行访问数据
再返回所对应的值
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 获取队列头部元素 QDataType QueueFront(Queue* q);在“ Queue.c "源文件中写到：
// 获取队列头部元素 QDataType QueueFront(Queue* q){assert(q);assert(q->size >0);//断言空指针//断言顺序表不能为空return q->front->data;}（8）获取队列尾部元素
这个很简单，直接用下标进行访问数据
再返回所对应的值
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 获取队列队尾元素 QDataType QueueBack(Queue* q);在“ Queue.c "源文件中写到：
// 获取队列队尾元素 QDataType QueueBack(Queue* q){assert(q);assert(q->size >0);//断言空指针//断言顺序表不能为空return q->tail->data;}（9）获取队列中有效元素个数
这个很简单
直接返回所对应的值
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 获取队列中有效元素个数 intQueueSize(Queue* q);在“ Queue.c "源文件中写到：
// 获取队列中有效元素个数 intQueueSize(Queue* q){assert(q);//断言空指针return q->size;}（10）检测队列是否为空
这个很简单
如果队列为空返回非零结果
如果不为空返回0
代码演示：（内有注释）
（其中 q 是一个指向队列的指针，下同）
在“ Queue.h "头文件中写到：
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps);在“ Queue.c "源文件中写到：
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 intQueueEmpty(Queue* q){assert(q);//断言空指针return q->size ==0;}三、完整代码实现
1. Queue.h
用于存放用来放函数的声明和一些库函数的头文件
#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>#include<sperror.h>//重定义，方便修改类型typedefint QDataType;//表示每个节点的类型typedefstructQListNode{ QDataType data;//节点中存储的数据structQListNode* next;//指向下一个节点的指针}QNode;// 队列的结构 typedefstructQueue{ QNode* front;//头指针 QNode* tail;//尾指针int size;//总元素个数}Queue;// 初始化队列 voidQueueInit(Queue* q);// 队尾入队列 voidQueuePush(Queue* q, QDataType data);// 队头出队列 voidQueuePop(Queue* q);// 获取队列头部元素 QDataType QueueFront(Queue* q);// 获取队列队尾元素 QDataType QueueBack(Queue* q);// 获取队列中有效元素个数 intQueueSize(Queue* q);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 intQueueEmpty(Queue* q);// 销毁队列 voidQueueDestroy(Queue* q);2. Queue.c
用于用来放函数的定义(队列的主体)
#include"Queue .h"// 初始化队列 voidQueueInit(Queue* q){assert(q);//断言空指针 q->front =NULL; q->tail =NULL; q->size =0;//全部初始化置 0 / NULL}// 队尾入队列 voidQueuePush(Queue* q, QDataType data){assert(q);//断言空指针 QNode* tmp =(QNode*)malloc(sizeof(QNode));//直接开辟一个节点的空间if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("malloc");return;}//没有问题后就赋值 tmp->data = data; tmp->next =NULL;//注意：当队列中没有节点时//此时插入的节点既是头节点，又是尾节点if(q->size ==0){ q->front = tmp; q->tail = tmp;}else{ q->tail->next = tmp; q->tail = tmp;} q->size++;}// 队头出队列 voidQueuePop(Queue* q){assert(q);assert(q->size >0);//断言空指针//断言顺序表不能为空//注意：当队列中只有一个节点时，头尾节点相等//此时将头节点和尾节点都释放if(q->size ==1){free(q->front); q->front =NULL; q->tail =NULL;}else{ QNode* del = q->front; q->front = q->front->next;free(del);} q->size--;}// 获取队列头部元素 QDataType QueueFront(Queue* q){assert(q);assert(q->size >0);//断言空指针//断言顺序表不能为空return q->front->data;}// 获取队列队尾元素 QDataType QueueBack(Queue* q){assert(q);assert(q->size >0);//断言空指针//断言顺序表不能为空return q->tail->data;}// 获取队列中有效元素个数 intQueueSize(Queue* q){assert(q);//断言空指针return q->size;}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 intQueueEmpty(Queue* q){assert(q);//断言空指针return q->size ==0;}// 销毁队列 voidQueueDestroy(Queue* q){assert(q);//断言空指针 QNode* cur = q->front;//遍历链表，一一释放空间销毁while(cur){ QNode* next = cur->next;free(cur); cur = next;} q->front = q->tail =NULL; q->size =0;//全部初始化置 0 / NULL}3. Test.c
用于测试实现的队列的运行效果
（这里是小编在写代码时写的测试用例）
（大家在写的时候也要多多测试哦）
#include"Queue .h"intmain(){ Queue Q;QueueInit(&Q);QueuePush(&Q,1);QueuePush(&Q,2);QueuePush(&Q,3);QueuePush(&Q,4);QueuePush(&Q,5);QueuePush(&Q,6);/*QueuePop(&Q); int ret1 = QueueFront(&Q); QueuePop(&Q); int ret2 = QueueFront(&Q); QueuePop(&Q); int ret3 = QueueFront(&Q); printf("%d %d %d\n\n", ret1, ret2, ret3);*/while(QueueEmpty(&Q)){printf("%d ",QueueFront(&Q));QueuePop(&Q);}printf("\n\n");QueueDestroy(&Q);return0;}结语
本期资料来自于：
OK，本期的队列详解到这里就结束了
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持
本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！
新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！
支持一下（三连必回QwQ）
