一.引言

想象一下我们在食堂排队买饭的画面，是不是在前面的人先离开，后免排队的后离开呢？这种 " 先进先出 " 的概念便是 队列 ，FIFO (First In First Out)。

---

二.核心概念

• 队头： 负责队列数据的删除
• 队尾：负责队列数据的添加

---

三. 方案的选择

顺序表or链表？

思考一下队列的实现用哪一个更合适呢？
相信你一定发现了问题，由于队列是一头入数据，一头出数据，如果选择顺序表那么在出队列时，需要将队列内全
部数据向前移动，这不但浪费时间并且顺序表的选择还会造成空间的浪费，而链表正好弥补了这两个缺陷

普通的顺序表实现队列，本质上是在 ‘挪动数据的痛苦’ 和 ‘空间浪费的无奈’ 之间做的选择。

---

四.对比思考：栈和队列的区别

比较维度	栈 (Stack)	队列 (Queue)
逻辑特点	后进先出	先进先出
实现方法	顺序表	链表
操作位置	仅栈顶	队头出，队尾入

---

五.核心功能的逻辑实现

1. 节点的构建与管理架构

我们使用链表来实现队列，所以需要有一个节点结构

typedef int QDataType;
typedef struct QNode
{
	struct QNode* next;//下一个节点
	QDataType val;
}QNode;

队列与链表又有所区别，因为需要控制两端的数据，所以我们需要两个指针来分别控制队尾和队头。

架构设计：封装的力量

所以定义两个指针来控制，但是此时如果想要完成初始化操作，则需要传入二级指针，因为若队列为空进行入队列操作时，会改变头结点的指向，一级指针无法做到。

	void QInit(QNode** phead, QNode** ptail);

这样操作起来非常麻烦且容易出错，观察发现这两个变量是相同的类型，所以我们再次定义一个结构体来承载这两个指针。

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;//后续有需要
}Queue;

这样做在后续操作中只需要传入Queue指针就可以访问到结构体内成员并更改内容。

2.标准初始化

//初始化
void QInit(Queue* q)
{
	assert(q);
	q->phead = NULL;
	q->ptail = NULL;
	q->size = 0;
}

3.动态入队列：尾插法

因为是先进先出，所以直接将数据插在尾部，用ptail来管理。

void QPush(Queue* q, QDataType x)
{
	assert(q);//断言传入参数非空
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;
	if (q->phead == NULL)
	{
		q->phead = q->ptail = newnode;
	}
	else
	{
		q->ptail->next = newnode;
		q->ptail = newnode;
	}
	q->size++;
}

先申请新节点，再进行尾插连接，操作与链表相同。

4.稳健出队：头删法

先进先出的特性，我们需要在头部进行删除数据。

void QPop(Queue* q)
{
	assert(q);
	assert(q->size);

	QNode* next = q->phead->next;
	free(q->phead);
	q->phead = next;
	q->size--;
}

边界的处理：

注意只剩一个节点时，再次执行头删操作，此时phead指向的节点被释放后phead置为空，但是ptail指针仍然指向原队尾地址成为野指针，所以如果后续要执行入队列操作时，ptail被解引用将造成内存泄漏问题。

//出队列
void QPop(Queue* q)
{
	assert(q);
	assert(q->size);

	QNode* next = q->phead->next;
	free(q->phead);
	q->phead = next;
	q->size--;
	if (q->phead == NULL)
	{
		q->ptail = NULL;
	}
}

小tips：注意要判断队列是否为空，若为空则无法进行Pop（什么也没有了，怎么删？）

5.状态检查：判空

bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

这时便体现出了我们在结构体封装时定义size的好处了，若size为空则证明队列内是空的。

6.元素访问：窥探队头与队尾

这里也很简单直接返回指针指向的节点内的值即可

//取队头数据
QDataType QFront(Queue* q)
{
	assert(q);
	assert(q->size);
	return q->phead->val;
}

//取队尾数据
QDataType QBack(Queue* q)
{
	assert(q);
	assert(q->size);
	return q->ptail->val;
}

小tips：注意要判断队列是否为空，若为空则无法取得数据

7.资源释放：内存的安全销毁

释放也相当so easy，只需要写一个循环函数，将链表内的节点一一销毁即可。

//队列的销毁
void QDestroy(Queue* q)
{
	assert(q);
	QNode* next = NULL;
	while (q->phead)
	{
		next = q->phead->next;
		free(q->phead);
		q->phead = next;
	}
	if (q->phead == NULL)
	{
		q->ptail = NULL;
	}
	q->size = 0;
}

当然你若是觉得这样销毁太过于麻烦，还可以借助我们的判空和出队列两个函数。

//升级版
void QDestroy(Queue* q)
{
	assert(q);
	while (!QEmpty(q))
	{
		QPop(q);
	}
}

只剩一个节点时，还要注意ptail野指针问题，与出队列逻辑一致。

源码仓库：
本文实现的代码已同步上传至我的 Gitee 仓库，欢迎自取或 Star ⭐️：
胡会元的26_exercise仓库

---

队列的本质是秩序，而当我们打破线性，走向分支与层级时，便进入了二叉树的世界。下一篇，我们来看看计算机是如何用‘两根树枝’撑起整个搜索与排序森林的

我们下期再见！