队列的概念
队列是一种特殊的线性结构
只允许在一端进行插入操作，在另一端进行删除操作，队列具有先进先出FIFO(First In First Out)
入队：进行插入操作，进行插入的一端称为队尾
出队：进行删除操作，进行删除的一端称为队头
队列的实现
因为队列在尾进在头出，如果用顺序表实现，那么出队就需要挪动顺序表的数据，效率低
所以队列用链表实现更好
我们先写一个链表的结构体：
typedef int QueueDataType; typedef struct QueueNode { struct QueueNode* next; QueueDataType data; }QNode;
在主函数中，为了方便，我们定义一个头指针head指向队头和尾指针tail指向队尾
QNode* head = NULL; QNode* tail = NULL;
1
2
如果这么写的话,在设计函数时，就要至少传2个指针，并且为二级指针，这是否的麻烦
所以我们可以再定义一个结构体，将head和tail都放到这个结构体中，那么设计函数时只需要传一个指针就可以了
typedef struct Queue { QNode* head; QNode* tail; int size; }Queue;
这样设计的话，函数中传这个结构体的参数，通过结构体指针就可以改变结构体了，所以也不用传二级指针了
这里在结构体内还定义了一个int size，这是表示队列的长度，这个设计并非多余，在后面的实现中就会发现这个size能提高效率
这里的队列实现需要定义2个结构体，这是在之前的数据结构中没有出现的
初始化
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
将head和tail都初始化为空，size为0
销毁
void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* nex = cur->next; free(cur); cur = nex; } pq->head = NULL; pq->tail = NULL; pq->size = 0; } 1
入队
入队，首先就是开辟一个新节点
QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; 1
然后就是入队了，在队尾入队
这里如果head==NULL，就说明当前队列还没有元素head和tail都为空
所以让head指向这个第一个节点，同时这个节点也是自己的尾，tail也应指向这个节点
pq->head = pq->tail = newnode;
1
如果head不为空，就说明当前队列中有元素，直接在tail后面插入新节点即可
void QueuePush(Queue* pq, QueueDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } 1 2
出队
出队，首先应用断言判断一下队列是否为空
assert(!QueueEmpty(pq));
1
在队头出队
首先用next指针保存head->next，然后就可以free掉head了，然后再将head指向新的头next
QNode* next = pq->head->next; free(pq->head); pq->head = next; 1 2
3
在这里会发现，如果队列只要一个节点，next为空，然后虽然能够让head为空，但tail不会被改变，所以我们需要改一下：
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; } 1
11
所以最终代码：
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); 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--; }
判空
bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
队列长度
int QueueSize(Queue* pq) { assert(pq); return pq->size; }
这里就最能看出在结构体中定义size的好处了
如果不去定义，那么在这里求长度就会遍历一遍队列，导致效率低
而之前定义了size，这里直接返回size即可，效率高
返回队头元素
QueueDataType QueueFront(Queue* pq) { assert(pq); return pq->head->data;
一般通过QueueFront和QueuePop2个函数来得到队列中的数据
打印队列中数据：
while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } 1
返回队尾元素
QueueDataType QueueBack(Queue* pq) { assert(pq); return pq->tail->data; }
