一、队列的概念以及结构
队列是只允许在一断进行入数据、在另一端进行出数据的特殊的线性表；队列遵循先进先出的原则，即FIFO（First In First Out），队列删除数据的一端是对头，增加数据的一端是队尾。
它的结构就像是排队的人群一样，先来的先走，后来的需要等待之前的走完再走；
## 队列的实现可以用数组，但是大多数情况下使用链表，因为在实现出数据（即头删）的时候，使用数组操作十分不便，需要移动数组其他的元素，此时时间复杂度相对较高，使得效率相对低下；但是链表的头删很方便。
二、队列的实现
学习完基本的链表之后，实际上很容易明白队列各个接口的逻辑；但是次数学习队列最重要的却是理解好新相对于前面链表新引入的结构；
1、头文件
#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* head;
QNode* tail;
int size;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//数据入队列
void QueuePush(Queue* pq, QDataType x);
//数据出队列
void QueuePop(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列的大小
int QueueSize(Queue* pq);## 为什么要定义Queue结构体？
在前面实现单链表或者是双向链表的时候，都是先在头文件里面定义好链表节点指针，这个操作在队列里面也是同样的，QNode结构体指针里面同样包含next指针和节点数据val；
而下面的Queue结构体存在的原因是这样的：首先队列的特点就是先进先出，出涉及到头节点，进涉及到尾节点，此时定义好一个结构体Queue让传参更为方便，只需要传Queue结构体指针就可以实现队列的基本操作了，并且最重要的一点是每次进行尾插的时候不需要找尾，我们知道单链表找尾需要遍历链表，效率较低，所以定义好一个队列结构体是优大于劣的；
当然不定义这个Queue结构体，而是在传参的时候传头节点，实现队列入数据的时候每次都找尾也可以。
可能你会说双向链表不是更好吗，既不用定义Queue结构体，也不用每次都遍历找尾，就能实现这个对列。当然如此，双向链表确实是最优的，但是研究问题和学习都是从对底层开始，单链表就是基本的链表。
2、队列接口的实现
###初始化队列
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
Queue结构体里面存放了队列的头节点和尾节点，每一个节点又都是一个节点结构体，这两个节点各自都有自己的数据域val和指针域next，在初始化的时候，首先传入的队列的地址不能为空，这时最基本的；
以前初始化链表的时候，传入的是一个节点地址。初始化是对节点里面的val和next初始化，在这里直接相当于是把两个节点指针置为NULL，为什么这样？传入的队列Queue类型的变量的head和tail指针还没有初始化，未初始化的指针是野指针，此时若是像初始化链表节点一样写成 pq->head(或是tail)->next(或是val)的时候相当于 对野指针解引用，这是非法的。所以这里先把对列的两个指针置为NULL；
这里定义一个size是为了记录对列里面元素的个数，避免需要知道队列里面元素的个数的时候还要遍历链表。
###队列的销毁
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
pq->size = 0;
if (pq->head != NULL)
{
free(pq->head);
}
if (pq->tail != NULL)
{
free(pq->tail);
}
pq->head = pq->tail = NULL;
}首先把size置为0；当head和tail不为空的时候才free，否则就是对NULL进行free操作了，这时非法的。
###队列入数据
//数据入队列
void QueuePush(Queue* pq, QDataType x)//单链表尾插
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->next = NULL;
newnode->val = x;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}入数据要对这个数据申请一个节点，入数据是在队尾，所以进行尾插操作；最后把size++。
###队列出数据
//数据出队列
void QueuePop(Queue* pq)//单链表头删
{
assert(pq);
assert(pq->size);
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--;
}出数据首先队列里面要有数据；一般的当队列里面有很多数据的时候，只需要进行简单的头删操作；但是若是队列里面只有一个数据的时候，此时若还是走else里面的一般头删方法会出问题，走else的话，一个节点的时候尾指针和头指针指向同一个节点，若是此时删除头节点只把头节点置为NULL却没有把为节点置为NULL，此时的尾指针就是野指针了；所以有if判断，如果只有一个节点，就把这个节点释放之后，把头、尾节点都置为NULL。
###获取队尾元素
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq && pq->size);
return pq->tail->val;
}###获取对头元素
//获取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq && pq->size);
return pq->head->val;
}###队列判空
//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0 ? true : false;
}###队列中的元素个数
//队列的大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
