（一）队列
队列：只允许在一端进行插入（队尾），在另一端进行删除（队头）操作的特殊线性表。
类比现实生活中的排队就餐，队尾加人（插入），队头拿到饭了出去（删除）。
具有先进先出的特质。
（二）队列的实现
我们选择单链表。
PS：
栈可以通过数组和链表来实现，但由于链表的尾插和尾删操作成本较高，故选择了数组；
队列同样可以通过数组和链表来实现，但由于数组的头删之后还要挪动数据，成本较高，故选择了单链表。
双向链表啥时候都能实现，但我们反而要去看数组和单链表是否可行。
因为双向链表空间成本较高。
代码实现：
//按照单链表的节点构造写 typedef int QDatatype; struct QueueNode { QDatatype val; struct QueueNode* next; }; typedef struct QueueNode QNode;（三）队列相关函数的实现
（1）尾插入队 QueuePush
void QueuePush(QNode** pphead,QNode** pptail,QDatatype x);当链表为空时，插入需要头结点，当链表不为空时，插入就只需要尾结点了，所以参数需要头尾结点；且需要改变实参，所以是二级指针传址调用。
比较一下：为啥单链表的插入操作中只传头结点，而不传尾结点？
入队插入函数传尾结点的意义是：以免每次进行尾插操作都要遍历查找尾结点，所以干脆把尾结点传给了入队的插入函数。
而在单链表的尾插中，我们就算传了尾结点也不顶用，我们还需要找到尾结点的前一个节点，难道还加一个参数prev？那就更麻烦了，所以我们干脆只传了头结点。（通过头结点，我们就能找到ptail和prev了，只不过每次都要遍历。）
从函数的参数观察，每次都要传两个二级指针，是不是太复杂了？
（复杂在于：需要传两个指针且指针还都是二级）
这里我们有一个很妙的思路：我们创建一个结构体，用于存放头结点指针和尾结点指针，再将结构体指针作为参数，传给函数。
结构体Queue的实现：
//Queue.h //头尾结点指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; }Queue; //入队声明 void QueuePush(Queue* pq, QDatatype x);因为函数中的插入操作会导致头结点尾结点的指针发生改变，所以我们才需要传递二级指针(QNode节点结构体的指针的指针)，在此处，我们将头结点指针和尾结点指针放在一个结构体中，头尾节点指针就成了结构体的一个成员变量，我们想通过函数真正改变结构体的成员变量，就只需要传递结构体指针，就行了。
这样就解决了一次性需要传两个二级指针的复杂参数问题。
写到这，不妨来回顾一下——
联想到双向链表的传参：
这和在双向链表中，我们传递哨兵位节点指针，一级就够了，而不用二级的底层逻辑是一样的。
在双向循环带头链表中，头插操作是将新节点插在哨兵位节点和第一个节点之间，并不是要改变哨兵位节点指针，而是改变哨兵位结构体节点的成员变量next指针，所以只需要传递哨兵位结构体节点指针，不需要传指针的指针(二级指针)了。
而这里密封的Queue结构体就类似于哨兵位的结构体。
但Queue结构体仍然存在优化空间。
在队列中有数元素个数的函数QueueSize，如果我们去遍历链表，则函数的时间复杂度为O(N)，但假如，在队列中存在像顺序表中的size一样的变量，我们只需要在入队函数中写一条size++，出队函数中写size--，则到调用QueueSize函数时，size不就已经代表了当下队列中的元素个数了吗？
这就避免了我们再去从头遍历带来的时间消耗。
代码优化：
//Queue.h //头尾结点指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //入队声明 void QueuePush(Queue* pq, QDatatype x);或许你会问：既然要加一个额外变量size，为啥是加在Queue结构体而不是QNode结构体里？
如果加在QNode结构体里，就是加在了节点里，那只要创建节点，每个节点中都需要再多一块空间存储size变量，岂不是造成更多的额外消耗？（N）；而在Queue结构体中，只会占一块空间。（1）
写到这，我们先来实现初始化函数。
（2）初始化 QueueInit
注意：初始化函数初始的是装了头尾结点和size的结构体Queue，而不是节点结构体QNode。
代码实现:
//Queue.c //初始化定义 void QueueInit(Queue* pq) { pq->phead = pq->ptail = NULL; pq->size = 0; }再回到入栈函数的实现中。
代码实现：
//队尾插入 void QueuePush(Queue* pq , QDatatype x) { assert(pq); //不再单独封装一个创建节点函数了，因为只需要在插入函数中写一次，没必要 QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->val = x; newnode->next = NULL; if (newnode == NULL) { perror("failed malloc"); return 0; } if (pq->phead == NULL) { //空链表的插入 pq->phead = pq->ptail = newnode; } else { //非空链表的插入 pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; //为QueueSize函数做准备 }在实现单链表时，我们封装了一个SLTBuyNode创建节点函数（头插、尾插、任意位置插入都需要创建新节点，封装成函数就能让程序更简洁），但在队列中，只有尾插入队函数需要创建新节点，所以不需要再额外封装一个创建节点函数。
我们说QNode节点结构体不需要初始化，为什么？
我们先来回顾一下顺序表的初始化，我们在测试源文件中创建了顺序表结构体变量sl并将其指针传给了STInit函数，顺序表结构体有了空间，我们就能对其中的成员变量arr、capacity和size进行初始化，可我们并不能对数组元素进行初始化，都没有malloc空间出来，根本就谈不上初始化。
而在链表中，我们在测试源文件中创建了单链表的节点结构体指针并置空，仅仅只是创建了结构体指针，而没有创建结构体节点变量，因为节点需要malloc创建，而我们还没有涉及malloc啊，那既然连结构体节点都没有创建，又何来初始化结构体成员这一说呢？
等到真正通过创建节点函数创建结构体节点后，在创建节点函数内部，我们就能对成员变量data和next进行了赋值操作，其实在我看来，这更像是初始化。
而初始化的本质就是赋值。
（3）头删出队 Queuepop
代码实现：
//队头删除 void QueuePop(Queue* pq) { //只要涉及删除，就一定要对链表判空 assert(pq); assert(pq->size > 0); if (pq->phead->next == NULL) { //仅剩一个节点 free(pq->phead); pq->phead = pq->ptail = NULL; } else { //多节点链表 QNode* del = pq->phead->next; free(pq->phead); pq->phead = del; } pq->size--; }分成单节点和多节点的情况是为了防止ptail变成野指针的情况。
其实多节点分支下的逻辑足以满足单、多节点的头删操作，仅仅只是等到链表变成空后，没有处理ptail，这样ptail就会变成野指针，为了防止这种情况，我们可以分成单、多节点的情况。
当然，也可以按照如下方式处理：
//队头删除 void QueuePop(Queue* pq) { //只要涉及删除，就一定要对链表判空 assert(pq); assert(pq->size > 0); //处理ptail野指针的另一种写法 QNode* del = pq->phead->next; free(pq->phead); pq->phead = del; if (pq->phead == NULL) pq->ptail = NULL; pq->size--; }不过也要注意，此时的if的条件判断是判空，而不是判断是否为单节点链表了。
（4）取队头节点val数据 QueueFront
注意：取队头节点val数据，仅仅只是取值，并没有涉及删除节点操作。
//取队头val数据 QDatatype QueueFront(Queue* pq) { assert(pq); //不能对空指针解引用 assert(pq->size > 0); //确保队列还能有节点能进行取值操作 return pq->phead->val; }当QueueFront和QueuePop搭配使用时，就能获取队列中的所有节点的val值。
判空总结：
顺序表：assert(ps->size)；
单链表：assert(*pphead)；
双向链表：assert(phead->next != phead)；
栈：assert(pst->size)；
队列：assert(pq->phead) / assert(pq->size)。
（5）取队尾节点的val数据 QueueBack
//取队尾节点的val数据 QDatatype QueueBack(Queue* pq) { assert(pq); assert(pq->size > 0); //assert(pq->ptail); return pq->ptail->val; }（6）数队列节点个数 QueueSize
//数队列节点个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }（7）判空 QueueEmpty
//判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }（8）队列的销毁 QueueDestory
//队列的销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next; //不提前保存pcur下一个节点，释放pcur后就找不到了 free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }（四）代码汇总：
//Queue.h #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDatatype; struct QueueNode { QDatatype val; struct QueueNode* next; }; typedef struct QueueNode QNode; //头尾结点指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //尾插入队声明 void QueuePush(Queue* pq, QDatatype x); //初始化Queue结构体声明 void QueueInit(Queue* pq); //出队头删声明 void QueuePop(Queue* pq); //取队头val QDatatype QueueFront(Queue* pq); //取队尾val QDatatype QueueBack(Queue* pq); //节点个数 int QueueSize(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //销毁队列 void QueueDestory(Queue* pq);//Queue.c #include"Queue.h" //初始化定义 void QueueInit(Queue* pq) { pq->phead = pq->ptail = NULL; pq->size = 0; } //队尾插入 void QueuePush(Queue* pq , QDatatype x) { assert(pq); //不再单独封装一个创建节点函数了，因为只需要在插入函数中写一次，没必要 QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->val = x; newnode->next = NULL; if (newnode == NULL) { perror("failed malloc"); return 0; } if (pq->phead == NULL) { //空链表的插入 pq->phead = pq->ptail = newnode; } else { //非空链表的插入 pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; //为QueueSize函数做准备 } //队头删除 void QueuePop(Queue* pq) { //只要涉及删除，就一定要对链表判空 assert(pq); assert(pq->size > 0); if (pq->phead->next == NULL) { //仅剩一个节点 free(pq->phead); pq->phead = pq->ptail = NULL; } else { //多节点链表 QNode* del = pq->phead->next; free(pq->phead); pq->phead = del; } pq->size--; //处理ptail野指针的另一种写法 /*QNode* del = pq->phead->next; free(pq->phead); pq->phead = del; if (pq->phead == NULL) pq->ptail = NULL;*/ } //取队头val数据 QDatatype QueueFront(Queue* pq) { assert(pq); assert(pq->size > 0); //assert(pq->phead); return pq->phead->val; } //取队尾节点的val数据 QDatatype QueueBack(Queue* pq) { assert(pq); assert(pq->size > 0); //assert(pq->ptail); return pq->ptail->val; } //数队列节点个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } //队列的销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }//Test.c #include"Queue.h" void Test01() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); while (!QueueEmpty(&q)) { printf("%d ",QueueFront(&q)); QueuePop(&q); } } int main() { Test01(); return 0; }测试源文件：
在顺序表中（数组），我们创建一个结构体类型变量SL sl进行测试；
在单链表和双向链表中，我们都是创建一个结构体节点指针变量STLNode* plist（第一个节点）/LTNode* plist（哨兵位节点）来进行测试；
在栈中（数组），我们创建一个结构体类型变量ST st 来进行测试；
在队列中（单链表），我们创建一个结构体变量类型Queue q来进行测试。
由于函数参数都需要pq（phead、ptail），所以创建Queue q是我们需要的。或许你会觉得这跟单链表创建plist的行为不同，但其实是一样的。
创建plist的本质就是创建了单链表的第一个节点，而创建Queue q也就是创建了单链表的第一个节点，因为Queue结构体中包含了phead。
出栈顺序：
在栈中，我们说数据入栈的顺序是1 2 3 4，但出栈的顺序却不只有4 3 2 1这一种，数据可以边进边出，所以数据出栈的顺序是有N种的。
但在队列中，只要数据入队的顺序是1 2 3 4，那么出队的顺序就只会是1 2 3 4这一种，即使是数据边进边出，也只有这一种。
可以来测试一下：
//Test.c #include"Queue.h" void Test01() { Queue q; QueueInit(&q); QueuePush(&q, 1); printf("%d \n", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 2); printf("%d \n", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 3); printf("%d \n", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 4); printf("%d \n", QueueFront(&q)); QueuePop(&q); while (!QueueEmpty(&q)) { printf("%d ",QueueFront(&q)); QueuePop(&q); } } int main() { Test01(); return 0; }——end——
