队列概念：

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

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

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

 

队列的实现 

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。 

 下面用链式结构实现队列：

// 链式结构：表示队列

typedef int QDataType;

typedef struct QListNode

{

        struct QListNode* next;//记录下一个节点地址

        QDataType data;//记录数据

}QNode;

// 队列的结构

typedef struct Queue

{

        QNode* head;//记录头节点

        QNode* tail;//记录尾节点

}Queue;

 开始先定义一个队列，要先进行初始化；

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
//开始没有数据的时候，把记录队首，队尾的节点都指向空

初始化完成就可以添加数据了，注意一定只能从队尾插入

两种情况：第一种，当添加前没有一个数据时，队首、队尾指针都要变化；

第二种，普通情况下只改变队尾指针即可；

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;
    //上面是开辟空间并赋值；

    //下面是两种情况
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

有入数据，就有出数据；第一种情况：出数据只要改变队首指针，

注意：第二种情况：当只有一个数据时，队首、队尾都要指向空指针；

要检验当队列中没有数据时，直接退出（或断言可以提示错误！）；

void QueuePop(Queue* pq)
{
    //保证，传入的数据不能为空，且队列不能为空；
	assert(pq);
	assert(pq->head);

    //下面是两种情况；
	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* ret = pq->head->next;
		free(pq->head);
		pq->head = ret;
	}
}

有时需要返回队首、队尾的数据，可以单独实现下接口：

//返回队首数据；
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

//返回队尾数据；
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

在一些项目中，要知道当前队列中的数据个数，以免多删除等操作造成崩溃

返回数据个数的接口如下：

int QueueSize(Queue* pq)
{
	assert(pq);

	//定义一个整形，初始化为0，遍历一遍链表
    int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}

	return n;
}

在判断队列数据为空的方法上，可以直接使用assert(pq->head);但是最好还是单独封装一个接口方便直接调用；接口直接返回真假；

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
    //如果相等返回真，也就是数据为空
    //如果不相等返回假，也就是数据不为空；谨慎使用；
}

因为是动态开辟的内存，最后要手动释放；

链表要遍历一遍，全部依次释放

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur= pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

上面实现的接口能满足大多数情况需要，具体情况具体分析；

来看一下如何来调用这些接口：

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 7);

	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	
	int n=QueueSize(&q);
	
	printf("%dn", QueueSize(&q));
    printf("%dn", QueueFront(&q));

	QueueDestroy(&q);
	return 0;
}