---

什么是队列

要弄明⽩什么是队列，我们同样可以⽤⼀个⽣活中的例⼦来说明。

假如公路上有⼀条单⾏隧道，所有通过隧道的⻋辆只允许从隧道⼊⼝驶⼊，从隧道出⼝驶出，不允许逆⾏。

因此，要想让⻋辆驶出隧道，只能按照它们驶⼊隧道的顺序，先驶⼊的⻋辆先驶出，后驶⼊的⻋辆后驶出，任何⻋辆都⽆法跳过它前⾯的⻋辆提前驶出。

队列（queue） 是⼀种线性数据结构，它的特征和⾏驶⻋辆的单⾏隧道很相似。不同于栈的先⼊后出，队列中的元素只能 先⼊先出 （First In First Out，简称 FIFO ）。

队列的出⼝端叫作 队头 （front），队列的⼊⼝端叫作 队尾 （rear）。

队列的结构

队列： 只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循 先进先出 原则。

入队列： 队列的插入操作叫做入队列，进行插入操作的一端称为队尾。

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

如下图所示👇

与栈类似，队列这种数据结构既可以⽤数组来实现，也可以⽤链表来实现。

⽤数组实现时，为了⼊队操作的⽅便，把队尾位置规定为最后⼊队元素的 下⼀个位置 。

队列的数组实现如下👇

队列的链表实现如下👇

1. 初始化队列

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

首先我们需要创建一个结点类型，类型包含了该 结点的数据 和 指向下一结点的指针。

📝 代码示例

typedef int QDataType;

// 链式结构：表示队列（记录每个结点）
typedef struct QueueNode
{
	QDataType data; // 结点的数据域
	struct QueueNode* next; // 结点的指针域
}QNode;

注意，队列与链表有所不同，普通链表只需要知道链表的头指针，而队列的信息包括了 队头 和 队尾，所以我们需要再创建一个结构体用于 存放队列的队头和队尾。

📝 代码示例

// 队列的结构 （找到队列的头和尾的）
//因为我们要控制队列，队列里面不止一个值，而是有多个值，要方便头删和尾插
typedef struct Queue
{
	QNode* head; // 队列的头指针
	QNode* tail; // 队列的尾指针
}Queue;

然后，我们对创建好的 队列 进行初始化。

📝 代码示例

//初始化队列 
void QueueInit(Queue* pq) {
	assert(pq); //队列可以为空，但是管理队列的头指针和尾指针不能为空
	pq->head = NULL;
	pq->tail = NULL;
}

所以创建好以后，此时为 空队列 ，head 和 tail 都指向 头结点 ，大致结构就是下面这样👇

2. 队尾入队列

⼊队（enqueue）就是把新元素放⼊队列中，只允许在队尾的位置放⼊元素，新元素的下⼀个位置将会成为新的队尾。

即申请一个 新结点 并将其 链接到队尾，然后 改变队尾的指针 指向即可。

Step 1，如下图所示👇

Step 2，如下图所示👇

注意：若队列中原本无数据，那么我们只需让队头和队尾均指向这个新申请的结点即可。
 

动图演示👇

📝 代码示例

//队尾入队列（尾插）
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);

	/*开辟一个新结点*/
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x; //把x赋给newnode的数据域
	newnode->next = NULL; //因为是尾插，所以尾部的结点的next要指向NULL

	/*如果头、尾都为空，那么说明队列还是空的，还没有结点*/
	if (pq->head == NULL && pq->tail == NULL) {
		assert(pq);
		pq->head = pq->tail = newnode;
	}
	else { //说明队列已经有结点了，直接到插入到尾部即可
		pq->tail->next = newnode; //把newnode链接到tail的next
		pq->tail = newnode; //然后让tail指向newnode
	}
}

3. 队头出队列

出队操作（dequeue）就是把元素移出队列，只允许在队头⼀侧移出元素，出队元素的后⼀个元素将会成为新的队头。

即 释放队头指针指向的结点 并改变队头指针的指向即可。若队列中只有一个结点，那么直接将该结点释放，然后将队头和队尾置空即可。

Step 1，如下图所示👇

Step 2，如下图所示👇

动图演示👇

📝 代码示例

//队头出队列 
void QueuePop(Queue* pq) {
	assert(pq);
	assert(pq->head && pq->tail); //队列的head和tail不能为空,不然怎么头删呢？

	//如果head的next为空，那么说明只有一个结点
	if (pq->head->next == NULL) {
		free(pq->head); //直接释放掉head
		pq->head = pq->tail = NULL; //然后把head和tail 置为空
	}
	else {
		QNode* next = pq->head->next; //保存头结点的下一个结点地址
		free(pq->head); /释放掉head
		pq->head = next; // 改变队头指针指向
	}
}

4. 获取队列头部元素

头部元素，即返回队列 头指针 指向的数据。若 队列 为空，则不能获取。

如下图所示👇

动图演示👇

📝 代码示例

//获取队列头部元素 
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->head); // 检查队列是否为空

	return pq->head->data; // 返回队头指针指向的数据
}

5. 获取队列队尾元素

尾部元素，即返回队列 尾指针 指向的数据。若 队列 为空，则不能获取。

如下图所示👇

动图演示👇

📝 代码示例

// 获取队列队尾元素 
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(pq->tail); //取队尾的数据，那么tail肯定不能为空

	return pq->tail->data; //返回队尾指针指向的数据
}

6. 获取队列中有效元素个数

队列中有效元素个数，即 队列中的结点个数。我们只需 遍历队列，统计队列中的结点数并返回即可。

📝 代码示例

// 获取队列中有效元素个数 
int QueueSize(Queue* pq) {
	assert(pq);
	
	QNode* cur = pq->head; //使用cur遍历整个队列
	int count = 0; //统计队列结点个数
	while (cur) { //当cur不为空,就进入循环,开始遍历
		count++;
		cur = cur->next;
	}
	return count; //返回队列中的结点数
}

注意：这个函数是队列里面最慢的函数，时间复杂度为 $O(N)$

7. 检测队列是否为空

检测队列是否为空，即判断 队头指针 指向的内容是否为空。

📝 代码示例

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq) {
	assert(pq);

	//如果head或者tail等于空，说队列为空
	return pq->head == NULL && pq->tail == NULL;
}

8. 销毁队列

队列中的每一个结点所占用的内存空间都是 动态开辟 的，当我们使用完队列后，需要及时释放队列中的每一个结点。

📝 代码示例

//销毁队列 
void QueueDestroy(Queue* pq) {
	assert(pq);
	
	QNode* cur = pq->head; //使用cur遍历整个队列
	QNode* next = cur->next; //存储cur的下一个结点
	
	while (cur) { //开始遍历队列
		free(cur); //释放掉cur
		cur = next; //把cur的下一个结点赋给cur
	}
	pq->head = NULL; //队头置空
	pq->tail = NULL; //队尾置空
}

9. 总结

总的来说，队列的实现还是比较简单的，⼊队和出队的时间复杂度，也都是 $O(1)$。

队列的应用：

队列的输出顺序和输⼊顺序相同，所以队列通常⽤于对 “历史” 的回放，也就是按照 “历史” 顺序，把 “历史” 重演⼀遍。
 
例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。
 
再如 ⽹络蜘蛛 实现⽹站抓取时，也是把待抓取的⽹站 URL 存⼊队列中，再按照存⼊队列的顺序来依次抓取和解析的。
 

接口函数贴图

最后附上一张完整的 双向链表 的 接口函数图