博客大纲
队列的定义
定义：
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的特性。
数据结构中的队列与现实中的排队十分相似，比如我们在食堂打饭，一定是先排队的人先拿到饭离开队伍，后来排队的人后离开队伍，即先进先出的特性，我用一张图来解释：
假设这是一个食堂的排饭队列，每当有新的元素进入队列，一定是从后面进队；而当有元素离开队伍，一定是靠近食堂窗口的元素先离开队列。
在这个过程中，进入元素的那一端被称为队尾，出元素的那一端被称为队头。
接下来我们用C语言来尝试实现这样一个结构：
队列
结构分析
既然队列本质上是一种基于线性表的结构，那么其就可以用同为线性表的数组，顺序表或者链表来承载。那么我们该如何抉择？
在此我选用了链表这一结构来实现队列，前两者都有一个大问题，就是由于内存必须连续，时间与空间一定会浪费一个。
不妨设想，如果我们用顺序表来实现，我们从队头删除一个元素，那么这个元素删除后留下的空间何去何从？
如果想把这个空间保留下来，那么就需要将所有元素前移一位，这样遍历队列会浪费大量时间，导致队列的效率降低。
如果我们选择放弃这一块空间，动态内存管理下的空间必须是整体开辟，整体释放的，也就是说，我们无法将一个元素的空间free掉。那么如果直接不free这个空间，那么他就会一直留在内存中，并且无法再存储数据。
而链表就可以同时保证时间与空间的高效利用，当我们需要删除一个元素，直接将其free掉，对其它节点的空间不会造成影响。当我们需要切换队头，只需要改变头部指针的指向即可，不必遍历数组。
若对链表不熟悉，可以看我介绍链表的博客：数据结构与算法：单链表，数据结构与算法：双链表。
我们用两个结构体来实现这个队列，其中第一个结构体是用于承载链表的节点的，第二个结构体则是储存队列的信息，相当于队列的”身份证“，我们用这个”身份证“来记录当前队列的队头，队尾，以及队伍的长度。结构如下：
typedef int QDataType;//用typedef来设置这个队列的元素类型 typedef struct QueueNode//链表的每一个节点 { QDataType val;//当前节点存储的值 struct QueueNode* next;//下一个节点的指针 }QNode; typedef struct Queue//队列的基本信息 { QNode* phead;//队头节点 QNode* ptail;//队尾节点 int size;//队列长度 }Queue;
结构图如下：
初始化接口
当用户想要使用我们的队列，那么用户首先需要创建一个队列，比如Queue q;就是创建了一个名为q的队列，队列创建好后，就有以下几个问题：
1.队列的空间在哪里?
Queue q;这个过程，其实只是创建了一个存储队列信息的结构体而已，相当于为一个还没有出生的婴儿先准备了一张身份证。由于婴儿还没出生，即空间还没有创建，我们不知道这个队列的信息，于是我们为其初始化一些值。在此我们要将phead与ptail初始化为空指针，而队列的大小初始化0。
代码如下：
//初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; }
由于队列q是用户自己再main函数中创建的，所以如果我们的接口想要修改这个队列的信息，那就需要传址调用，此处使用Queue* pq作为参数，即传入了队列q的地址。
2.我们什么时候创建空间？
链表想要开辟空间，无非就是每插入一个节点，就开辟一个节点的空间，而我们插入节点，只能在尾部插入，也就是说，对于整个队列的实现，我们只需要在尾插这个接口中实现空间的开辟。此处初始化的时候不开辟空间，就是因为此时还没有存入任何元素，也就不需要空间来承载元素。
接下来我们就来实现尾插接口，并解决空间开辟这一问题。
入队接口
入队分为三个步骤：
1.将节点创建出来
2.将节点插入队伍中
3.更新队列的信息（即修改队列的”身份证“）
创建节点：
要将节点创建出来，无非就是malloc一个节点的所需空间，并对其赋值。
一个节点的结构体有两个成员，一个成员用于存储当前节点的值，另一个节点存下一个节点的地址。对于前者，直接赋值即可，那么我们当前节点的指针应该指向哪里？
由于我们的队列只能尾插，所以新的节点一定是尾部节点，尾部节点的next指针只需要置空即可。
此外，由于malloc函数在开辟空间时，是有可能开辟失败的，此时malloc有可能会返回一个空指针，所以我们在malloc开辟空间后，要判断其是否为空，如果为空，就退出程序，防止后续对空指针访问，导致错误。
代码如下：
QNode* newnode = (QNode*)malloc(sizeof(QNode));//开辟一个节点的空间 if (newnode == NULL)//判空，防止对空指针访问 { perror("malloc fail"); return; } newnode->val = x;//对此节点赋值 newnode->next = NULL;//将指针置空
将节点插入队伍中：
当我们创建好一个节点后，这个节点还不在队伍中，为了将其插入队伍，我们就需要将原先的队尾的指针指向这个新开辟的节点。即pq->ptail->next = newnode;。
但是这么做有一个问题，ptail一定可以访问吗？当我们的队列是一个空队列的时候，此时ptail是一个空指针，队空指针访问next，此时编译器就会报错。所以我们要将队列中没有元素的情况分类讨论：
当我们的phead为空，那么就说明此时队列为空，此时的尾插操作，其实就是将新节点赋值给phead，相当于在头部插入了一个元素。但实际上完成的是尾插。
代码如下：
if (pq->phead == NULL)//没有元素特殊处理 { pq->phead = newnode; } else { pq->ptail->next = newnode; }
更新队列信息：
在尾插过程中，由于队尾更新了，毫无疑问的我们要将ptail指向新的节点。而插入一个元素，队伍就会变长，所以我们的size也要加一。所以最后我们只需要：pq->ptail = newnode; pq->size++;即可。
最终代码如下：
//入队 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; //-----以上完成一个新节点的创建-----// if (pq->phead == NULL)//没有元素特殊处理 { pq->phead = newnode; } else { pq->ptail->next = newnode; } //-----以上完成将节点插入队列中-----// pq->ptail = newnode; pq->size++; //-----以上完成更新队列的信息-----// }
出队接口
由于队列的定义，在出队时也只能从头部出队。
出队需要以下操作：
1.检查队列是否有元素可删
2.删除元素
3.更新队列信息
检查队列是否有元素可删：
在删除一个节点的过程中，就要保证当前有元素可以出，如果是一个空队列，就没有出队的必要，所以我们要对其断言assert(pq->phead);，当phead为空，就说明此时队列中没有元素，那么断言就会报错，防止后续的操作造成程序错误。
确保队列有元素可删之后，就要开始删除元素了。
删除元素：
删除节点，其实就是将第一个节点给free掉。但是此时就需要面对一个问题，那就是：第二个节点的指针在第一个节点中，当我们free掉了第一个节点，我们就会丢失维护第二个节点的指针。所以我们要使用一个临时变量来保存节点，此处就不细讲了，在链表的章节中有详细的图文讲解。
代码如下：
QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); • 1 • 2 • 3
调整队列信息：
由于我们删除节点后，队伍长度就减小了，所以size需要减一。
那我们是否需要调整ptail指针？
这分为两种情况
当删除前，队列中有两个及以上的节点时：
由于我们在free节点之前，phead指针就已经被指向了下一个节点，此时节点2就是新的头节点，而尾部节点没有发生过改变，所以ptail指向是正确的，无需再调整ptail。
当删除前，队列中只有一个节点时：
由于phead在free之前时，会指向下一个节点，此时phead就指向了空指针，但是这是符合定义的，因为我们在删除唯一节点之后，队列就是空队列了，此时phead和ptail都应该是空指针。
但是目前最大的问题并不是ptail没有变成空指针，而是此时的phead指向了一块被释放的空间，变成了一个野指针，这是一个十分危险的操作，所以我们最后要将ptail的指向空。
通过上述分析我们可以得出：当队列只剩一个元素，就需要将ptail置空。
所以我们需要额外的判断，来判断队列在删除前有几个元素。此时我们只需要对phead是否为空判断即可：当phead在free完成后是空指针，就说明free之前只有一个节点，那么就需要将ptail置空。
代码如下：
if (pq->phead == NULL) pq->ptail = NULL; pq->size--;
最终此接口的代码如下：
//出队 void QueuePop(Queue* pq) { assert(pq); assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); if (pq->phead == NULL) pq->ptail = NULL; pq->size--; }
除了上述两个接口，以下接口的实现就非常简单了：
查找队头接口
这个接口就十分简单了，由于我们持有队列的头指针，只需要直接访问头指针的val成员即可：pq->phead->val;。
不过在那之前，是要确保队列中有元素，如果队列中没有元素，自然就访问不到队头，所以需要额外的断言assert(pq->phead);来确保当前队列有元素。
代码如下：
//查队头节点 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; }
队列判空接口
什么时候队列为空？
我们在前面多次分析过，只要队列为空。phead和ptail就是空指针。当然也可以通过size，当size为0也说明当前队列为空。
代码如下：
//判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
求队列长度接口
由于我们的队列中，是存有队列的长度的，所以我们只需要直接返回队列的size即可。
代码如下：
//求队长 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
销毁队列接口
销毁队列分为以下步骤：
1.将所有节点free
2.更新队信息
将所有节点free：
既然要将所有队列元素都释放掉，那我们就需要得到每一个节点的指针，此时我们就需要遍历队列。利用一个临时的cur指针，每释放完一个节点，就走到下一个节点。知道cur遇到空指针，说明已经将队尾前的所有元素都释放掉了。
更新队信息：
由于我们free掉了队列中的所有元素，此时队列就是一个空队列了，对于空队列，我们要将phead，ptail置空，size要变为0。
代码如下：
//销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
代码展示
Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //插入（只能尾插） void QueuePush(Queue* pq, QDataType x); //出队（只能头出） void QueuePop(Queue* pq); //查队头节点 QDataType QueueFront(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //求队长 int QueueSize(Queue* pq);
Queue.c
#include "Queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } //入队 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->phead == NULL)//没有元素特殊处理 { pq->phead = newnode; } else { pq->ptail->next = newnode; } pq->ptail = newnode; pq->size++; } //出队 void QueuePop(Queue* pq) { assert(pq); assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); //当只有一个节点的时候，phead，ptail与del指向同一块空间，free掉del后，ptail是野指针 if (pq->phead == NULL) pq->ptail = NULL; pq->size--; } //查队头节点 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } //求队长 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
test.c
#include "Queue.h" int main() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); QueuePush(&q, 7); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } QueueDestroy(&q); return 0; }
博客制作不易，还请留下一个免费的赞！
有问题欢迎指出，博主非常喜欢讨论问题！
