1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.队列的实现

队列可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，因为要从后面向前进行覆盖数据。

队列图示结构：

注释：由于队列的实现和链表的实现很多都是一样的！因为此处队列就是由链表实现的，队列的插入就是链表的尾插，队列的删除就是链表的头删，并没有太多的新意，在此前的链表的模拟实现中已经做出详细的讲解，此处不再多做缀解！希望大家能够自己模拟实现，如果有不懂的可以参照一下丸丸的代码，当然丸丸的代码只供参照，还有优化的空间，比如加上哨兵位之类的！

Queue.h头文件：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue*pq,QDataType x);
void QueuePop(Queue*pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);

Queue.c源文件

#include"Queue.h"
void QueueInit(Queue* pq)//队列的初始化
{
	assert(pq);
	pq->head =pq->tail = NULL;
}
QNode* BuyQNode(QDataType x)//开辟一个节点
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("fail malloc\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueuePush(Queue* pq, QDataType x)//入队
{
	assert(pq);
	QNode* newnode = BuyQNode(x);
	if (pq->tail == NULL)//没有节点的时候
	{
		assert(pq->head == NULL);
		pq->head= pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	
}
void QueuePop(Queue* pq)//出队
{
	assert(pq);
	assert(pq->tail&&pq->head);
	if (pq->head->next==NULL)//处理只有一个节点的时候
	{
		free(pq->tail);
		pq->tail = pq->head = NULL;
	}
	else//有多个节点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
size_t QueueSize(Queue* pq)//求队列的元素数目
{
	assert(pq);
	size_t size = 0;
	QNode* cur = pq->head;
	while (cur!= pq->tail->next)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
QDataType QueueFront(Queue* pq)//求队列首节点存储的元素
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)//求队列尾节点存储的元素
{
	assert(pq);
	assert(pq->tail);
	return pq->tail->data;
}
void QueueDestory(Queue* pq)//销毁队列
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
bool QueueEmpty(Queue* pq)//判断队列是否为空
{
	assert(pq);
	return pq->head==NULL&&pq->tail==NULL;
}