本篇总结队列是如何实现的，以及各方面的细节问题，比较链表与队列之间的不同，注意到不同的类型，要按照不同需求来定义结构，不能一成不变，印象刻板。
【队列】
⏰.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）的特点。
入队列：进行插入操作的一端叫做队尾
出队列：进行删除操作的一端叫队头
⏰.队列的实现
队列可以用数组和链表来实现。但使用链表的结构更优一些，因为如果使用数组结构，删除数据需要挪动大量数据，效率比较低。
队列我们使用链表来实现
首先使用链表定义一个结点
我们都知道结点是由一个结构体定义的，这个给结构体里有个指向下一个结点地址的next和数据data。
但想一下，队列需要对链表进行尾删，也就是每次都要找到尾结点，将链表的头结点和尾结点传给出队列函数，然后进行出队列操作，这样传参数就传好几个，不如让我们将头结点的地址和尾结点的地址分装成一个新的结构体
想一想为什么这里要给个尾指针过去呢？
如果在实现单链表操作中也给尾指针呢？
单链表中给尾指针能完成操作吗？尾插操作需要尾指针，这个操作可以完成，但尾删呢？尾删操作你给个尾指针就能完成吗？当然不能，还需要尾指针前面的结点地址。传个尾指针过去只能完成部分操作，不能完成全部操作还不如不传，代码挫的一批。
但这里不一样，这里队列有它自己的规则：那就是只在一端进行入队，那就是队尾，也就是说在队尾只进行尾插，不进行尾删，所以这里传尾指针过去是可以完成队列所需要的操作的，
要区别单链表中只传一个头指针，而队列这里要传头指针和尾指针的不同，我们要按照需要来定义不同结构。
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDatatype; typedef struct QNode//定义结点结构 { struct QNode* next; QDatatype data; }QNode; typedef struct Queue//将头指针和尾指针分装起来，传给队列操作函数 { QNode* head;//链表头指针 QNode* tail;//链表尾指针 int size;//大小想一想传过去有什么好处？ }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestroy(Queue* pq); //队尾入队列 void QueuePush(Queue* pq,QDatatype x); //队头出队列 void QueuePop(Queue* pq); //获取队列的有效数据的大小 void QueueSize(Queue* pq); //判断队列是否为空，如果为空返回非0，如果为非空返回0 bool QueueEmpty(Queue* pq); //获取队列头部元素 QDatatype QueueFront(Queue* pq); //获取队尾元素 QDatatype QueueBack(Queue* pq);
🕐1.初始化队列
首先对传入的数据进行初始化，我们知道传过来的是个分装好的结构体，里面有链表头指针，尾指针，大小。
所以一开始我们需要将头指针尾指针和大小都置0；
//初始化队列 void QueueInit(Queue* pq) { assert(pq);//首先断言判断是否传错 pq->head = pq->tail = NULL; pq->size = 0; }
🕑2.队尾入队列
队尾入队列，实际上就是链表的尾插。
而这正是这操作我们将链表的尾指针也传过去，就是为了每次尾插不需要找尾，每次插入时更新下尾指针位置即可。
//入队列 void QueuePush(Queue* pq, QDatatype x) { assert(pq);//断言是否传错 //入队，就是尾插一个结点，首先生成一个新结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->next = NULL;//需要置空，不然会出现野指针 newnode->data = x;//将数据赋值 if (newnode == NULL)//判断是否开辟成功 { perror("malloc"); } //因为为单链表，不带哨兵头，所以一开始head和tail都为空，第一步直接将结点赋值过去，然后后面才是真正的尾插 if (pq->head == NULL) { pq->head = pq->tail = newnode;//将结点赋值过去 } else { //尾插 pq->tail->next = newnode; pq->tail = newnode;//找尾--更新 } pq->size++;//插入一个数据size就要++ }
🕒3.队头出队列
对头出队列，本质上就是链表的头删，头删就是让头指针不断改变，然后让头指针前面的结点释放。
注意点1：
在删除数据之前我们都要对队列进行检查，看是否队列为空。
注意点2：要注意tail是指向最后一个结点的指针。
当head指向最后一个结点后释放，那么tail指向的空间被释放，那tail就变成野指针了，所以最后需要将tail置NULL。
有两中方式：
第一种：只管头删，最后再将tail置NULL
第二种：一开始就考虑二种情况，最后一个结点之前，和最后一个结点，即分为一个结点和多个结点。
//出队列 void QueuePop(Queue* pq) { assert(pq); //在删除数据之前需要考虑队列是否为空; assert(!pq->head==NULL); QNode* next = pq->head->next;//记录头结点后面的结点 free(pq->head);//是否头节点 pq->head = next;//将头指针重新指向后面的结点 //注意如果最后head和tail指向同一个结点，也就是最后一个结点时，tail会变成野指针。 //方法1： if (pq->head == NULL) { pq->tail = NULL; } pq->size--; }
方法2：
void QueuePop(Queue* pq) { assert(pq); //在删除数据之前需要考虑队列是否为空; assert(!pq->head==NULL); //注意如果最后head和tail指向同一个结点，也就是最后一个结点时，tail会变成野指针。 if (pq->head->next == NULL) { //直接释放最后一个结点 free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next;//记录头结点后面的结点 free(pq->head);//是否头节点 pq->head = next;//将头指针重新指向后面的结点 } pq->size--; }
🕓4.获取队列头部元素
获取队头数据，就直接将头结点的数据拿走即可，不过在拿之前需要进行判断队列是否为空，如果为空，那还拿什么
//获取队头数据 QDatatype QueueFront(Queue* pq) { assert(pq);//断言判断是否传错 assert(!QueueEmpty(pq));//判断是否为空 return pq->head->data;//队头数据 }
🕔5.获取队列尾元素
和获取队头数据一样需要判断队列是否为空
//获取队尾数据 QDatatype QueueBack(Queue* pq) { assert(pq);//断言判断是否传错 assert(!QueueEmpty(pq));//判断是否为空 return pq->tail->data;//队尾数据 }
🕕6.获取队列中有效元素的个数
看，最开始的问题即将揭晓，在分装的结构体中加上size的作用是什么？
加上size后我们就可以快速获取队列中有效元素的个数了，如果没有加上，要获取个数，那必须对链表进行遍历，时间复杂度就是O(N)，而现在就是O(1)。同样在单链表中我们如果想快速获得链表中有效数据的个数，也可以将节点与size分装成一新的结构体。那样就可以啦。
有的人想在带有哨兵头的链表中快速获取个数的办法是将size放入哨兵头里，想着反正哨兵头也不存储数据，就想着将size放进去，但是可以吗？
当然不可以，我们定义的链表中数据的类型有时是知道的，有时是不知道的，当数据类型是int类型是哨兵头里面可以放size，但当链表使用的数据类型是char？ double 类型时，你放进去一个int类型的size进去？可以吗？
void QueueSize(Queue* pq) { assert(pq); return pq->size; }
🕖7.检查队列是否为空
bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
🕗8.销毁队列
与头删类似，就是循环删除。当删除为空时，停止
然后将数据都置0
//销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } //保存下一个释放，保存下一个释放 pq->head = pq->tail = NULL; pq->size = 0; }
