【初阶数据结构】深入解析队列:探索底层逻辑

请添加图片描述

🔥引言

本篇将深入解析队列:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。

请添加图片描述
Alt

🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏：初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志我自踏雪至山巅
请添加图片描述

文章目录

一、队列的概念及结构
二、实现队列的相关接口(Stack.h)
- 2.1 队列初始化
- 2.2 队尾入队列
- 2.3 队头出队列
- 2.4 获得队列头部元素
- 2.5 获得队列尾部元素
- 2.6 获取队列中有效元素个数
- 2.7 检测队列是否为空
- 2.8 打印队列数据
- 2.9 队列的销毁
三、循环队列

一、队列的概念及结构

队列是指只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出 FIFO(First In First Out) 这一点跟栈的先进后出是相反的

入队列:进行插入操作的一端并且称为队尾
出队列：进行删除操作的一端并且称为队头

队列可用通过数组或链表结构实现，一般推荐使用链表实现更优一点。如果使用数组实现在出队列时，需要挪移大量数据，效率较低

这里采用链表结构实现队列

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/ 在这里插入图片描述

在这里插入图片描述

在设计队列结构中，需要设计两个指针去控制队列各节点的情况。head(队头指针)指向实际对头元素，taill(队尾指针)，指向实际队尾元素，增加一个变量size用于统计元素个数，由于存在多种信息，可以使用结构体统一管理

在这里插入图片描述

二、实现队列的相关接口(Stack.h)

在这里插入图片描述

2.1 队列初始化

void QueueInit(Queue *pq)//所以导致了需要初始化
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

这里需要注意的是:这里不需要对于节点进行初始化，在创建节点时会完成对应的初始化工作。

2.2 队尾入队列

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->phead == NULL)
	pq->phead = pq->ptail = newnode;
	else
	{
		(pq->ptail)->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

这里需要注意的是:首先就是空间开辟失败，然后需要搞清楚我们申请空间是给谁使用的，这里是为节点开辟空间。而不是为Queue结构体对象开辟空间，这里节点之间连接是通过节点指针进行连接

2.3 队头出队列

void QueuePop(Queue* pq)
{
	assert(pq && pq->phead);

	Qnode *del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del == NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

这里需要注意的是:当队列为空时，意味着头指针为空，那么尾指针也需要置成空

2.4 获得队列头部元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

2.5 获得队列尾部元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}

2.6 获取队列中有效元素个数

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

2.7 检测队列是否为空

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

2.8 打印队列数据

void QueuePrint(Queue* pq)
{
	assert(pq);
	while (!QueueEmpty(pq))
	{
		printf("%d->", QueueFront(pq));
		QueuePop(pq);
	}
}

这里需要注意的是:这里不能用cur，因为cur是不会动的，phead在pop的时候一直移动

2.9 队列的销毁

void QueueDestroy(Queue* pq)
{
	assert(pq);
	Qnode* cur = pq->phead;
	while (cur)//删除的作用
	{
		Qnode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->ptail = NULL; pq->phead = NULL;
	pq->size = 0;
}

这里需要注意的是:这里cur不要手动置空，会跳出循环，需等待cur自动指向空。