队列

• 队列的概念
• 队列的实现过程
• 队列的结构体与接口函数的定义
• 队列的接口实现
• • ①初始化队列(QueueInit)
  • ②队尾入队列(QueuePush)
  • ③队头出队列(QueuePop)
  • ④队头元素(QueueFront)
  • ⑤队尾元素(QueueBack)
  • ⑥有效元素个数(QueueSize)
  • ⑦检测队列是否为空(QueueEmpty)
  • ⑧销毁队列(QueueDestroy)
• 结语

队列的概念

什么是队列呢？我们先看下面的图：

我们可以理解成高速公路上的隧道，根据这个图的描述
我们把需入队的元素看作一辆车，把队列看作隧道，由此我们可以看出
队列的特点是只允许从一端进入，从另一端离开。
队列就是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

关于队列的相关名词：

入队：进入队列，即向队列中插入元素
出队：离开队列，即从队列中删除元素
队头：允许出队（删除）的一端
队尾：允许入队（插入）的一端
队头元素：队列中最先入栈的元素
队尾元素：队列中最后入栈的元素

我们可以直接将队头元素看作队头，队尾元素看作队尾。

队列的实现过程

和栈一样，队列也可以有两种实现方式：数组实现的顺序队列和链表实现的链队列，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
1.数组实现队列
数组队列的实现主要有以下两个缺点：
内存浪费：用于存储队列元素的数组空间永远不能用于存储该队列的元素，因为元素只能在前端插入，并且 front 的值可能很高，以至于， 在那之前的所有空间，永远无法填满。
数组大小：在某些情况下，如果我们使用数组来实现队列，可能需要扩展队列以插入更多元素，扩展数组大小几乎是不可能的，因此确定正确的数组大小总是一个 队列的数组实现中的问题。
因此在这我们不详细介绍，主要介绍链表实现队列的形式。
2.链表实现队列
链表实现的队列形式我们主要用图的形式来表现，看下图：

队列的结构体与接口函数的定义

队列的结构体定义
代码如下：

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

这里我们使用两个结构体嵌套，QueueNode包含了元素和下一级指针，Queue则在QueueNode基础上嵌套了头指针和尾指针记录入队和出队的操作。
队列的接口函数定义
代码如下：

void QueueInit(Queue* pq);// 初始化队列
void QueuePush(Queue* pq, QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列队头元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
int QueueSize(Queue* pq);// 获取队列中有效元素个数
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回ture，如果不为空返回false
void QueueDestroy(Queue* pq);// 销毁队列

接下来我们就将这几个接口函数来一一实现。

队列的接口实现

①初始化队列(QueueInit)

代码如下：

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

初始化没什么好讲的，就是头尾为空就ok。

②队尾入队列(QueuePush)

代码如下：

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

首先使用malloc函数动态分配内存，将x赋给newnode的data，下一级指针指向空，
下面分两种情况讨论，第一种是队列为空时，将newnode这个临时结点直接赋给头指针和尾指针，第二种情况是已经有元素的情况下，就将newnode赋给尾结点的next，再将尾指针指向新的结点，完成尾插操作

③队头出队列(QueuePop)

代码如下：

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//断言队列不为空

	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

这里的断言在下面的代码会实现，首先我们要将队头的下一结点赋给临时结点next，
然后释放掉头队头内存空间，再把临时结点next赋给新的队头指针，再考虑删完的情况下，把队尾结点也置空，完成出队操作。

④队头元素(QueueFront)

代码如下：

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//断言队列不为空

	return pq->head->data;
}

同样断言不为空，然后直接返回头指针的data元素即可。

⑤队尾元素(QueueBack)

代码如下：

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

队尾元素也和上面一样，首先断言队列不为空，再直接返回队尾指针的data元素即可。

⑥有效元素个数(QueueSize)

代码如下：

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

	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}

	return n;
}

这里我们创建一个临时结点cur，将队头结点赋给它，然后利用while循环对队列进行遍历，临时变量n进行记录，最后返回n的值即为有效元素个数。

⑦检测队列是否为空(QueueEmpty)

代码如下：

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

和前面的栈的接口函数一样，这个函数返回类型可以是int，这里我使用bool类型也是一样的，只不过我这返回的是逻辑值true或是false，如果为空返回ture，如果不为空返回false。

⑧销毁队列(QueueDestroy)

代码如下：

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

	pq->head = pq->tail = NULL;
}

销毁队列的实现和链表是一样的(本来这里的队列就是用链表实现的），首先将队头结点指针赋给临时结点cur，然后遍历每个队列结点，一个一个释放内存空间，最后将队头结点和队尾结点指向空，完成销毁链表操作。

结语

扩展：，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。这里我们就不讲这么多啦，如果大家有兴趣的话，作者可以单独写一篇博客来讲一讲。

制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！