数据结构第八弹---队列

2024-01-07 19:51:26

1、队列的概念和结构

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

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

在这里插入图片描述
如何实现队列?
队列是一种一端插入一端删除的数据结构,所以最好的实现方式是头删尾插效率高或者头插尾删效率高

1.数组实现:尾插和尾删效率较高,不太适合。
2.单链表实现:头删尾插效率较高,链表头删,链表尾插。

前面单链表提到尾插之前需要找到尾结点,为什么此处又说尾插效率高呢?
因为我们可以在定义结构的时候创建一个记录尾结点的变量,这样我们每次尾插的时候就不需要找尾结点了。
3.双向链表实现:头插头删尾插尾删效率都较高,可以实现队列。
双向链表头插头删尾插尾删效率都较高,为什么此处不直接使用双向链表实现呢?
因为单链表就能很好的实现一个队列,而双向链表相较与单链表会多开辟一个结点,在空间方面会有更多的消耗,所以一般不推荐使用双向链表实现队列。

2、队列的实现

经过上述的分析,我们推荐使用单链表实现队列,那么接下来就由博主来实现一下队列。
在这里插入图片描述
首先创建一个工程。(下图为vs 2022)
在这里插入图片描述
Queue.h(队列的类型定义、接口函数声明、引用的头文件)
Queue.c(队列接口函数的实现)
test.c (主函数、测试顺序表各个接口功能)

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

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

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

以下是博主创建的队列结构,可以根据自己的喜好创建喔。
建议:创建结构时最好能通俗易懂,最好不用拼音创建。
在这里插入图片描述

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、销毁

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

在这里插入图片描述

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;//头结点为空则返回真
}

测试
在这里插入图片描述

2.5、入队

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

画图分析如下
在这里插入图片描述
代码实现

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;//将尾结点更新
	}
}

测试
在这里插入图片描述

2.6、出队

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

在这里插入图片描述
代码实现

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;//更新头结点
	}
}

测试
在这里插入图片描述

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

2.7、获取队头数据

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

代码实现

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

测试
在这里插入图片描述

2.8、获取队尾数据

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

代码实现

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

测试
在这里插入图片描述

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

2.9、获取有效数据个数

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

代码实现

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

测试
在这里插入图片描述

3、代码汇总

以下是Queue.h的代码。

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


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;
}

总结

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

文章来源:https://blog.csdn.net/2201_75584283/article/details/135315570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。