一. 什么是队列

队列（Queue）是一种常见的数据结构，它遵循 “先进先出” 原则，只允许在一段进行插入数据操作，在另一端进行删除数据操作，进行插入操作的一端称为队尾，进行删除操作的一端称为对头。
例如在食堂排队打饭，先来的人先打到饭，后来的人排在队尾，这就是队列的典型应用。

队列主要应用于：

• 任务调度系统： 任务调度系统用于在指定时间或周期性执行代码逻辑，例如定时生成报表、同步数据或触发自动化任务。
• 消息队列处理： 消息队列通过异步通信机制解耦系统组件，支持任务分发、流量削峰和事件驱动架构。
• 广度优先搜索： BFS按层级遍历图或树结构，适用于最短路径查找和连通性分析。
• 缓冲区管理： 缓冲区通过临时存储数据减少I/O操作频率，平衡高速处理与低速设备间的速度差异。

二. 队列的基本操作

• 入队(Push)： 向队尾添加元素
• 出队(Pop)： 从队头移除元素
• 获取队头(Front)： 获取队头元素但不移除
• 获取队尾(Back)： 获取队尾元素
• 判空(Empty)： 检查队列是否为空
• 队列个数(Size)： 获取队列个数

三. 队列的代码实现

1. 队列的链式结构

• 由两个结构体构成，一个是由头节点、尾节点和队列个数组成，另一个是每一个节点的值和指向下一个节点的指针组成。

typedef int QDataType;//int类型更改别名为QDataType
//节点结构
typedef struct QueueNode
{
	QDataType val;          //指向节点的值
	struct QueueNode* next; //指向下一个节点的指针
}QNode;
//队列结构
typedef struct Queue
{
	QNode* phead;//队头
	QNode* ptail;//队尾
	int size;//队列大小
}Queue;

2. 队列的初始化和销毁

• 初始化队列的phead和ptail为NULL。
• 销毁队列，循环遍历每一个节点并释放掉内存,以避免内存泄漏，把元素个数size更改为0。

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

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* pcur = pq->phead;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

3. 队列的插入和删除

• 队尾插入：malloc一块空间，指向下一个节点的指针置为NULL，给节点赋值为X，判断队列是否为空，为空时头节点和尾节点同时指向这块空间，不为空时尾节点的下一个节点指向这块空间并更新尾节点，成功插入元素时队列个数size加1。
• 队头删除：判断队列是否为空，不为空时，判断队列是否只有一个元素（phead == ptail），只有一个元素时释放内存，头节点和尾节点置为NULL，有多个节点时头节点指向下一个节点并释放头节点内存，成功删除元素时队列个数size减1。

//队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;

	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

//队头删除
void QueuePop(Queue* pq)
{
	assert(pq && pq->size > 0);
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

4. 取队头元素

• 通过头节点指针指向节点的值。

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq && pq->size > 0);
	return pq->phead->val;
}

5. 取队尾元素

• 通过尾指针指向节点的值。

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq && pq->ptail);
	return pq->ptail->val;
}

6. 判断队列是否为空

• 当队列个数size为0时，队列为空。

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

7. 队列的元素个数

• 直接返回队列个数size.

//队列个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

总结

通过以上讲解，相信大家都能更好的掌握队列的使用了，在使用队列时需要注意是一些问题，入队时判断到队列为空时不要忽略了头节点的指向，出队时检查队列是否为空。大家还需自己动手编写代码加深记忆。感谢各位大佬们的阅读，在文章中如有错误的地方大家可以给博主评论，博主一定改正。感谢大家的点赞、收藏、评论和收藏。

---

【数据结构】——顺序表链表（超详细解析！！！）
【数据结构】——栈（Stack）的原理与实现
力扣（LeetCode) ——有效的括号(C语言）
力扣（LeetCode) ——移除链表元素(C语言）