数据结构第八弹---队列_网站优化分享

您的位置：上海毫米网络优化公司 > 网站优化分享 >

队列

1、队列的概念和结构
2、队列的实现

2.1、头文件包含和结构定义
2.2、初始化
2.3、销毁
2.4、判断是否为空
2.5、入队
2.6、出队
2.7、获取队头数据
2.8、获取队尾数据
2.9、获取有效数据个数
3、代码汇总

总结

1、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性
表，队列具有先进先出FIFO(First In First Out) 的原则。

入队列：进行插入操作的一端称为队尾

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

数据结构第八弹---队列,在这里插入图片描述,第1张

如何实现队列？

队列是一种一端插入一端删除的数据结构，所以最好的实现方式是头删尾插效率高或者头插尾删效率高。

1.数组实现：尾插和尾删效率较高，不太适合。

2.单链表实现：头删尾插效率较高，链表头删，链表尾插。

前面单链表提到尾插之前需要找到尾结点，为什么此处又说尾插效率高呢？

因为我们可以在定义结构的时候创建一个记录尾结点的变量，这样我们每次尾插的时候就不需要找尾结点了。

3.双向链表实现：头插头删尾插尾删效率都较高，可以实现队列。

双向链表头插头删尾插尾删效率都较高，为什么此处不直接使用双向链表实现呢？

因为单链表就能很好的实现一个队列，而双向链表相较与单链表会多开辟一个结点，在空间方面会有更多的消耗，所以一般不推荐使用双向链表实现队列。

2、队列的实现

经过上述的分析，我们推荐使用单链表实现队列，那么接下来就由博主来实现一下队列。

数据结构第八弹---队列,在这里插入图片描述,第2张

首先创建一个工程。(下图为vs 2022)

数据结构第八弹---队列,在这里插入图片描述,第3张

Queue.h（队列的类型定义、接口函数声明、引用的头文件）

Queue.c（队列接口函数的实现）

test.c （主函数、测试顺序表各个接口功能）

2.1、头文件包含和结构定义

以下是实现队列可能用到的头文件。

#include
#include
#include
#include

以下是博主创建的队列结构，可以根据自己的喜好创建喔。

建议：创建结构时最好能通俗易懂，最好不用拼音创建。

数据结构第八弹---队列,在这里插入图片描述,第4张

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next; //存放下一个结点指针
	QDataType data;         //存放数据
}QueueNode;
typedef struct Queue
{
	QueueNode* head;//头结点
	QueueNode* tail;//尾结点
}Queue;

2.2、初始化

链表的结构是通过动态开辟的空间，可以先不初始化。但是队列的结构是在栈区开辟的，为了防止越界访问，需要先初始化为NULL。

void QueueInit(Queue* pq)
{
	assert(pq);//防止空指针传入
	pq->head = pq->tail = NULL;//初始化为空指针，防止野指针问题
}

2.3、销毁

队列是通过动态开辟的内存，需要手动释放，即依次遍历将结点空间释放，并手动置空。
思想：定义一个变量用来找结点，不为空则释放然后找下一个结点，为空则结束。

数据结构第八弹---队列,在这里插入图片描述,第5张

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;//养成创建变量习惯，为了后面能找到头结点
	while (cur)
	{
		QueueNode* next = cur->next;//标记下一个结点
		free(cur);
		cur = next;//更新结点
	}
	pq->head = pq->tail = NULL;//释放完手动置NULL
}

2.4、判断是否为空

根据队列的初始化函数可知，在创建之前会将头结点置空，所以头结点为空则队列为空。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//头结点为空则返回真
}

测试

数据结构第八弹---队列,在这里插入图片描述,第6张

2.5、入队

入队：即在队尾处插入数据。

画图分析如下

数据结构第八弹---队列,在这里插入图片描述,第7张

代码实现

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)//动态开辟后记得判断喔！
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)//没有数据情况
	{
		pq->head = pq->tail = newnode;//将新结点赋值给头尾结点
	}
	else//有数据情况
	{
		pq->tail->next = newnode;//尾结点下一个插入数据
		pq->tail = newnode;//将尾结点更新
	}
}

测试

数据结构第八弹---队列,在这里插入图片描述,第8张

2.6、出队

出队：即在队头位置删除数据。
前提：有数据才能出队

数据结构第八弹---队列,在这里插入图片描述,第9张

代码实现

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//确保有数据
	//一个元素
	if (pq->head->next == NULL)
	{
		free(pq->head);//释放空间
		pq->head = pq->tail = NULL;//手动置空
	}
	//多个元素
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);//释放空间
		pq->head = next;//更新头结点
	}
}

测试

数据结构第八弹---队列,在这里插入图片描述,第10张

队头元素就是头结点中存储的数据

2.7、获取队头数据

队头数据：即头结点数据。

代码实现

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

测试

数据结构第八弹---队列,在这里插入图片描述,第11张

2.8、获取队尾数据

队尾元素就是队尾结点的数据

代码实现

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

测试

数据结构第八弹---队列,在这里插入图片描述,第12张

将队列遍历一遍，计算大小

2.9、获取有效数据个数

有效数据个数：即有效结点个数。
思想：从头结点开始计算，不为空则size++，然后更新到下一个结点，为空则结束。

代码实现

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

测试

数据结构第八弹---队列,在这里插入图片描述,第13张

3、代码汇总

以下是Queue.h的代码。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
typedef struct Queue
{
	QueueNode* head;//头结点
	QueueNode* tail;//尾结点
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(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);

以下是Queue.c的代码

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("QueueNode fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

网站制作设计教程创建一个网站的流程网络营销策划书模板哪家做网站的公司好网站建立具体步骤是江门网站建设制作

上一篇：Java-扑克牌的创建以及发放

下一篇：【Rust】——所有权：Stack（栈内存）vs Heap（堆内存）（重点）