前言：

在上一章中我们使用数组实现了数组栈各接口功能的实现，对各接口的原理和工作方式有了一定了解，而今天，在这节课我们将使用链表来实现队列的相关接口功能。现在我们进入今天的学习。

一、队列概述：

1.队列的概念：

队列是一种特殊的线性表，它允许在表的的前端进行删除，而在表后端进行插入操作，也就是先进先出。它和栈一样，队列也是一种操作说限制的线性表。进行插入操作的一端称之为队尾，进行删除操作的端称之为对头。

队列的元素又叫队列元素。在队列中插入一个队列元素称之为入队，从队列中删除一个队列元素称之为出队。

二、队列的各种接口功能实现：

队列的实现也可以用数组，但是我们一般通过链表来实现，因为链表实现会更好。

1.初始化队列：

①.执行操作之前需要进行非空判断，防止对空指针进行操作。

②.判断非空之后，只需要将头指针与尾指针置空，和size赋值0就可了。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;

}

2.入队（尾插）：

①.执行操作之前需要进行非空判断，防止对空指针进行操作。

②.判断非空之后，申请新节点，并向新节点中存入数据，存入之后进行插入。

③.节点插入时需分两种情况进行讨论，一种是在队列为空时，及内部无有效数据，此时只需要让头指针与尾指针都指向新节点即可，是新节点成为队列中唯一有效数据。另外一种就是当队列中有有效数据时，此时首先时原本为尾节点的next指向新节点，再更新尾节点就可以了。
void QueuePush(Queue* pq,QDatatype x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL && pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

3.出队（头删）：

①.执行操作之前需要进行非空判断，防止对空指针进行操作。

②.再出队之前应需要对队列内容量进行判断，方队没有有效数据的空队列进行错误操作。

③.满足条件之后，使第二节点成为第一节点，再释放第一节点，同时注意对操作后将队列删空的情况进行区别处理。
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	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--;

}

4.查看队头：

①.执行操作之前需要进行非空判断，防止对空指针进行操作。
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));


	return pq->head->data;
}

5.查看队尾

①.执行操作之前需要进行非空判断，防止对空指针进行操作。
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(QueueEmpty(pq));

	return pq->tail->data;
}

6.查看队列大小：

①.执行操作之前需要进行非空判断，防止对空指针进行操作。
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

7.判断队列是否为空:

①.执行操作之前需要进行非空判断，防止对空指针进行操作。
int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
这里也可以直接返回队列是否为空的判断结果：
bool QEmpty(Q* pq)
{
    assert(qp);
    return qp->head==NULL;
}

8.队列的销毁：

①.执行操作之前需要进行非空判断，防止对空指针进行操作。

②.从头结点开始，遍历释放所有节点，最后再将头指针和尾指针进行置空。
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}