“海色温柔，波浪缓慢，似乎在静静期待着新的一天。”
前言：
上期我们讲了栈，它的特点是“后入先出”。这次我们再来学习一个新的数据结构：队列，它的特点是“先入先出，后入后出”，准备好了吗？开始！
Part1: 何为队列
1.队列的概念
队列队列，顾名思义，就像排队买饭，排在前面的人买到饭先走，排到后面的人需要等待... ...
下面是队列的正经概念：
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出原则(First In First Out) 。
进行插入操作的一端称为队尾，
进行删除操作的一端称为队头。
2.队列的结构
我是图示
Part2: 队列的实现
1.前期准备
1.1创建项
不解释：
Queue.h：头文件，声明所有函数；
Queue.c：源文件，实现各函数；
Test.c： 源文件，主函数所在项，可调用各函数。
1.2队列结构
仍然是那个问题：用什么结构来实现队列较好？
数组：？删除元素要整体移动，时间复杂度高，且动态扩容比较麻烦，不推荐；
链表：插入删除数据后无需修改中间部分的元素，方便在队头和队尾操作，推荐。
那么选双链表还是单链表呢？
若选择双链表，的却方便找尾，但是仅仅为了找尾方便而选择它，未免会显得臃肿；
选择单链表呢，轻巧简洁，只需解决找到尾部的问题即可，有一个巧妙的方法就是：
在队列的结构中 定义尾指针 。
我们捋一遍：
就队列的整体来说：需要首尾指针和大小（长度）；
就队列中的一个结点来说：需要下一个结点的指针和要存储的数据。
欸？相比栈来说，是不是结构更加复杂了？
是的，这意味着要多定义一个结构体，两个结构体之间是包含关系：
我是图示
上代码：
typedef int QDataType; //队列中的结点 typedef struct QListNode { struct QListNode* next; QDataType data; }QNode; //队列整体 typedef struct Queue { QNode* head; QNode* tail; int size; }Queue;
1.3队列初始化
要从整体上把握，把首尾指针初始化为空，大小初始化为 0 即可：
// 初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
2.功能实现
2.1队头出队列
队头出队列，队列中是一定至少有一个结点的，但其实还是要分两种情况考虑的：
一是只有一个结点，直接把这个结点释放掉，再将首尾置空即可；
二是有两个及以上个结点，除了释放头部的结点，还需要把队头指针指向下一个结点；
最后莫忘大小减一。
// 队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); //pq->head = NULL; pq->head = next; } pq->size--; }
2.2队尾入队列
要入队列，首先要先申请一个新的结点（注意是结点，不是队列）；
再申请完并初始化后，就需要插入了：
也是两种情况：
一是链表为空，此时只要将首尾指针修改为新结点指针即可；
二是链表不为空，就要用到尾指针，将尾结点的下一个结点修改为新结点，并且更新尾结点指针；
最后莫忘大小加一。
// 队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* tailNode = (QNode*)malloc(sizeof(QNode)); if (tailNode == NULL) { perror("malloc fail"); return; } tailNode->next = NULL; tailNode->data = x; if (pq->head == NULL) { pq->head = pq->tail = tailNode; } else { pq->tail->next = tailNode; pq->tail = tailNode;//掉 } pq->size++; }
2.3获取队列头部元素
进行了插入操作，当然要看看数据怎么样啦
这个比较简单，直接返回头部数组即可
// 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head && pq->tail); return pq->head->data;//NULL }
2.4获取队列尾部元素
同上：
// 获取队列队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head && pq->tail); return pq->tail->data; }
2.5获取队列中有效元素个数
还记得之前定义的 size 吗？
在这里它就展现出重要作用了：
// 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
2.6判断队列是否为空
为空返回非 0 ，不是空就返回 0；
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* pq) { return pq->size == 0; }
2.7销毁队列
思路就是把整个队列遍历一遍，释放每个结点，再把首尾指针置空，大小归 0 即可：
// 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { free(cur); cur = cur->next; } pq->head = pq->tail = NULL; pq->size = 0; }
总结：
其实相比栈来说，队列只是在结构上复杂了一些，其他的操作与单链表的操作就非常相似了。
