引言：于本篇博客当中，我们将讲到数据结构——队列的有关知识。而对于这次的队列，我们将会在单链表的基础上实现。
更多有关C语言和数据结构知识详解可前往个人主页：计信猫
一，队列的含义
队列是一种特殊的线性表，它只允许在表的一端进行插入数据的操作，另一端进行删除数据的操作。
队头：进行数据删除的一端
队尾：进行数据插入的一端
所以，队列便可以用如下的图进行表示：
而正因为队列遵循FIFO原则（即先进先出），使得入队列与出队列的顺序一一对应，也就多被应用于广度优先遍历的操作。
二，队列结构体的定义
老样子，我们仍然使用三文件操作法，分别创建Queue.h、Queue.c、test.c三个文件。
因为先前提到，队列会在单链表的基础上实现，那么我们就需要先定义一个单链表结构体：
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
但是，因为在队列之中，我们只需要关注队列中队头和队尾的两个节点即可，并且为了避免二级指针的使用难以理解，所以我们选择再定义一个结构体Queue用于储存队列的队头和队尾两节点。
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;//记录队列中的节点个数
}Queue;包含可能用到的头文件后，我们的Queue.h的代码内容如下：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;//记录队列中的节点个数
}Queue;三，队列数据操作函数
1，队列的初始化
队列的初始化与其他数据结构的初始化别无它异，我们只需要将结构体中的指针类型初始化为NULL，整型类型初始化为0就可以了。直接上代码：
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->phead = q->ptail = NULL;
q->size = 0;
}2，队列的尾插
对于队列的尾插，其实也就和单链表的尾插一模一样。我们只需要使用malloc函数申请一个节点的空间，然后将新创建的节点连在队列的尾部，同时将ptail指针移到新形成的队尾，最后的最后，一定不要忘记size++。这样，一个队列的尾插函数就成功写出了。
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点
if (newnode == NULL)
{
perror("malloc fail!");
return;
}
newnode->next = NULL;
newnode->val = data;
//队列元素为0个时
if (q->ptail == NULL)
{
q->phead = q->ptail = newnode;
}
//队列有元素时
else
{
q->ptail->next = newnode;
q->ptail = newnode;
}
q->size++;
}3，队列的头删
因为队列只可以在队头进行数据删除，所以队列就只有一个头删函数。
如上图所示，对于队列的头删函数，我们需要首先创建节点结构体指针next记录队头的下一个节点的地址，以免队头被free掉之后导致的后续节点的丢失，然后我们再将phead指针赋值为next，最后再进行size--即可。
但是有一个特殊情况，当队列只有一个节点的时候，我们进行队列的头删之后，ptail则会变成野指针，这时候我们就需要特殊处理，将ptail也赋值为NULL，防止野指针的出现。如图：
综上所述，我们的队列头删函数如下：
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->size > 0);
QNode* next = q->phead->next;
free(q->phead);
q->phead = next;
//特殊情况：队列只有一个节点的时候
if (q->phead == NULL)
{
q->ptail = NULL;
}
//勿忘size--
q->size--;
}4，获取队列头部数据
这时候，我们所创建的Queue结构体就派上大用场了，因为这个结构体直接就保存了我们的phead节点，所以我们直接使用就可以了。代码如下：
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->phead);
return q->phead->val;
}5，获取队列尾部数据
那么这个函数，也就跟前一个函数相差不大了。都是直接使用Queue结构体就可以了，我们直接上代码：
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->ptail);
return q->ptail->val;
}6，获取队列有效元素个数
在Queue结构体中，我们早就使用了size来记录有效元素的个数，所以我们直接返回size的值即可。
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}7，判断队列是否为空
该函数的返回值为布尔类型，即true和false。
队列为空，返回：true
队列不为空，返回：false
对于队列是否为空，我们只需要判断size是否为零就可以了。所以代码如下：
// 检测队列是否为空
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
//若size等于零，则表达式为真，则队列为空
//若size不等于零，则表达式为假，则队列为假
}8，队列的销毁
因为我们创建队列时使用了malloc函数，故为了防止内存溢出，我们需要创建一个队列的销毁函数，来完成释放队列申请的空间的操作。
在该函数中，我们需要再创建一个QNode结构体指针cur用于保存即将被释放的节点的下一个节点的地址，以防止地址的丢失，然后再使用free函数释放掉节点即可。最后的最后，勿忘将size置为零。
所以我们的代码如下：
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* next = q->phead;
while (next)
{
QNode* cur = next->next;
free(next);
cur = next;
}
q->size = 0;
}
