数据结构队列的实现

在这里插入图片描述
本章介绍数据结构队列的内容，我们会从队列的定义以及使用和OJ题来了解队列，话不多说，我们来实现吧

队列

1。队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
我们来看一下下面的这张图，让我们更好的理解它
在这里插入图片描述
我们从队尾入，队头出，只能是这样入栈和出栈

2。队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，效率会比较低。

那队列的实现我们是用链式结构来实现的，因为用数组下标的话，出栈的时候要往前挪动数据，会更麻烦，这样队列的意义就下降了，所以我们这里用的方法是链式结构。

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType* next;
	QueueDataType data;
}QueueNode;

typedef struct Queue
{
	QueueDataType* head;
	QueueDataType* tail;
}Queue;

这里我们定义的结构体Queue有很大的作用，因为队列不是像单链表那样，队列是有它的特点的，其中最大的一个特点就是入栈只能从尾入，出栈就是头出，所以我们在这里定义head和tail有很大的作用，定义在结构体当中会方便不少，那我们现在继续往下看我们的接口函数吧。

给大家看一下下面实现队列的接口函数，然后我们一步一步的来实现他们

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

队列的初始化

void QueueInit(Queue* q);

初始化我们初始的是结构体Queue中的内容

void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
}

首先要判断传过来的指针是否是为空，然后将头指针和尾指针都置为NULL。

销毁队列

void QueuePush(Queue* q, QueueDataType data)

首先我们要创造一个节点将它放入，创造节点的结构体就是QueueNode，然后我们要更新后面节点中的head和tail，这里大家肯定有疑问，我们竟然是更新指针，那我们应该传指针的地址才能起到作用，一级指针只能改变结构体的内容，那我们在这里传的话，难道不会产生问题吗？答案是不会，我们的结构体中放的就是指针，那我们只需要改变结构体的内容，就是head和tail就行，竟然是这样的话，我们传一个一级指针就可以起到我们的作用，所以传的是一级，那现在我们在插入函数中先创造一个节点，因为只能从队列的尾插入，而且有了这个指针，我们就不需要像单链表那样再去找尾，我们每次插入都会更新尾。

void QueuePush(Queue* q, QueueDataType data)
{
	assert(q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}

有了入栈就有出栈，出栈的话是从我们的队列最开始的地方出队，我们来实现一下吧！

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* headnext = q->head->next;
	free(q->head);
	q->head = headnext;

}
/

这里的空是因为如果我们的队列都是空的话，我们哪里还有数据进行删除呢
所以要先检查一下是不是为空，那接着我们把这个函数也实现一下吧

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}

这个很好理解，如果为空就代表一个数也没有，那我们就不能再对队列进行操作了，那再来看我们下面的接口函数吧。

// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
	assert(q);
	return q->head->data;
}

有头就有尾，希望我们的人生也是
那我再来实现一下取尾的接口吧

QueueDataType QueueBack(Queue* q)
{
	assert(q);
	return q->tail->data;
}

我们继续往下走，实现一下我们后面的接口函数，这些基本上都很简单，我就也不再解释了，看代码就能理解的

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

销毁队列

void QueueDestroy(Queue* q)
{
	while (!QueueEmpty(q))
	{
		QueueNode* headnext = q->head->next;
		free(q->head);
		q->head = headnext;
	}

}

统计我们队列节点的数量我们遍历一遍就可以实现了，定义一个cur指针进行遍历，那其他的我们也都讲完了，后面分享栈和队列的OJ题给大家，看完之后对队列有了更深的理解

完整代码

#include"Queue.h"

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{
	assert(q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}
// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* headnext = q->head->next;
	free(q->head);
	q->head = headnext;

}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
	return q->head->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{
	return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	int count = 0;
	QueueNode* cur = q->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	while (!QueueEmpty(q))
	{
		QueueNode* headnext = q->head->next;
		free(q->head);
		q->head = headnext;
	}

}


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

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType* next;
	QueueDataType data;
}QueueNode;

typedef struct Queue
{
	QueueDataType* head;
	QueueDataType* tail;
}Queue;

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

今天的分享就到这里了，我们下次再见

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/92451.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Android JNI系列详解之生成指定CPU的库文件

Android JNI系列详解之生成指定CPU的库文件

一、前提 这次主要了解Android的cpu架构类型&#xff0c;以及在使用CMake工具的时候&#xff0c;如何指定生成哪种类型的库文件。 如上图所示&#xff0c;是我们之前使用CMake工具默认生成的四种cpu架构的动态库文件&#xff1a;arm64-v8a、armeabi-v7a、x86、x86_64&#xff0…
阅读更多...
【Unity】【Amplify Shader Editor】ASE入门系列教程第二课 硬边溶解

【Unity】【Amplify Shader Editor】ASE入门系列教程第二课 硬边溶解

黑色为0,白色为1 新建材质&#xff08;不受光照影响&#xff09; 拖入图片 设置 添加节点&#xff1a; 快捷键&#xff1a;K 组合通道&#xff1a;快捷键 V 完成图
阅读更多...
Golang struct 结构体注意事项和使用细节

Golang struct 结构体注意事项和使用细节

结构体所有字段在内存当中是连续的 type Point struct {x, y int }type Rect struct {leftUp, rightDown Point }func main() {//r1会在内存当中有四个整数r1 : Rect{leftUp: Point{x: 1,y: 2,},rightDown: Point{x: 3,y: 4,},}//r1有四个int&#xff0c;在内存当中是连续分布的…
阅读更多...
MES管理系统如何让传统汽车行业从“制造”走向“智造”

MES管理系统如何让传统汽车行业从“制造”走向“智造”

在传统制造业中&#xff0c;“数字化转型”是一个老生常谈的话题&#xff0c;然而&#xff0c;许多传统制造业仍处于“信息化”的阶段&#xff0c;距离真正的数字化还有很长的路要走。如果要在所有传统制造行业中寻找那些可以成为转型“先行者”的领域&#xff0c;那么深度与广…
阅读更多...
Golang Gorm 一对多关系 关系表创建

Golang Gorm 一对多关系 关系表创建

一对多关系 我们先从一对多开始多表关系的学习因为一对多的关系生活中到处都是&#xff0c;例如&#xff1a; 老板与员工女神和添狗老师和学生班级与学生用户与文章 在创建的时候先将没有依赖的创建。表名称ID就是外键。外键要和关联的外键的数据类型要保持一致。 package ma…
阅读更多...
让eslint的错误信息显示在项目界面上

让eslint的错误信息显示在项目界面上

1.需求描述 效果如下 让eslint中的错误&#xff0c;显示在项目界面上 2.问题解决 1.安装 vite-plugin-eslint 插件 npm install vite-plugin-eslint --save-dev2.配置插件 // vite.config.js import { defineConfig } from vite import vue from vitejs/plugin-vue import e…
阅读更多...
linux Firewalld学习笔记

linux Firewalld学习笔记

1、Firewalld默认策略 默认情况会阻止流量流入&#xff0c;但允许流量流出。 2、Firewalld区域概念 拒绝区域drop、默认区域public、允许区域trusted 3、区域规则 区域与网卡接口 默认区域规则 常用的有trusted &#xff08;相当于白名单&#xff09;、work/public 区、…
阅读更多...
软考：中级软件设计师:OSI/RM七层模型，网络技术标准与协议

软考：中级软件设计师:OSI/RM七层模型，网络技术标准与协议

软考&#xff1a;中级软件设计师:OSI/RM七层模型 提示&#xff1a;系列被面试官问的问题&#xff0c;我自己当时不会&#xff0c;所以下来自己复盘一下&#xff0c;认真学习和总结&#xff0c;以应对未来更多的可能性 关于互联网大厂的笔试面试&#xff0c;都是需要细心准备的…
阅读更多...
MySQL数据库 索引、事务、储存引擎

MySQL数据库 索引、事务、储存引擎

索引 索引的概念 索引是一个排序的列表&#xff0c;在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址&#xff08;类似于C语言的链表通过指针指向数据记录的内存地址&#xff09;。 使用索引后可以不用扫描全表来定位某行的数据&#xff0c;而是先通过索引表找…
阅读更多...
昇腾Ascend+C编程入门教程（纯干货）

昇腾Ascend+C编程入门教程（纯干货）

2023年5月6日&#xff0c;在昇腾AI开发者峰会上&#xff0c;华为正式发布了面向算子开发场景的昇腾Ascend C编程语言。Ascend C原生支持C/C编程规范&#xff0c;通过多层接口抽象、并行编程范式、孪生调试等技术&#xff0c;极大提高了算子的开发效率&#xff0c;帮助AI开发者低…
阅读更多...
pdf太大怎么压缩大小？这样压缩文件很简单

pdf太大怎么压缩大小？这样压缩文件很简单

工作和学习中&#xff0c;用到PDF文件的机会还是比较多的&#xff0c;但有时候PDF文件过大会给我们带来困扰&#xff0c;比如上传PDF文件时会因超出系统大小导致无法上传&#xff0c;这时候简单的解决方法就是压缩PDF文件&#xff0c;下面就来看看具体的操作方法吧~ 方法一&…
阅读更多...
构造函数内的方法 直接写在构造函数内部 与 写在prototype上 的区别

构造函数内的方法 直接写在构造函数内部 与 写在prototype上 的区别

文章目录 前言区别总结 前言 以前没注意过, 去创建一个构造函数的时候, 方法都是直接写在函数内的. 在构造函数需要多次实例化的情况下有缺点, 不过幸好以前项目里的构造函数也不需要多次实例化, 缺点没有生效. 区别 为了比较, 先在构造函数内部直接书写方法, 查看实例化结果…
阅读更多...
时间和日期--Python

时间和日期--Python

1. 时间&#xff1a;time模块 总结&#xff1a;2. datetime模块 相比与time模块&#xff0c;datetime模块的接口更直观、更容易调用 2.1 datetime模块定义的类 &#xff08;1&#xff09;datetime.date:表示日期的类。常用的属性有&#xff1a;year、month、day; &#xff…
阅读更多...
docker compose iceberg 快速体验

docker compose iceberg 快速体验

https://iceberg.apache.org/spark-quickstart/#docker-compose port&#xff1a;8888
阅读更多...
SpingMVC拦截器-用户登录权限控制分析

SpingMVC拦截器-用户登录权限控制分析

视频链接&#xff1a;08-SpringMVC拦截器-用户登录权限控制代码实现2_哔哩哔哩_bilibili 114 1、做了一个用户跟角色添加的相关操作 1.1 这个后台工程&#xff0c;没有进行相关操作也能够进行登录&#xff1a; 2、现在我做一个用户的权限控制&#xff0c;如果当前我没有进行操…
阅读更多...
VUE笔记（三）vue的语法

VUE笔记（三）vue的语法

一、计算属性 1、计算属性的概念 计算属性是依赖于源数据(data或者属性中的数据)&#xff0c;在元数据的基础上进行逻辑运算后得到的新的数据&#xff0c;计算属性要依赖于源数据&#xff0c;源数据数据变化计算属性也会变化 2、计算属性的语法 在vue2中使用computed这个选…
阅读更多...
2024年天津市大学软件学院专升本专业课考试大纲

2024年天津市大学软件学院专升本专业课考试大纲

天津市大学软件学院2024年“高职升本科”联合招生专业考试大纲 一、考试性质 天津市大学软件学院“高职升本科”联合招生专业考试是由合格的高职高专毕业生参加的选拔性考试。学校根据考生的成绩&#xff0c;按照已确定的招生计划&#xff0c;德、智、体全面衡量&#xff0c;…
阅读更多...
mysql 查询的字段值太长显示不全 group_concat

mysql 查询的字段值太长显示不全 group_concat

当前这个字段非常的长&#xff0c;在数据库看的时候也只是显示一部分内容&#xff0c;这是由于group_concat的group_concat_max_len参数的值太小造成的&#xff0c;默认值如下&#xff1a; show VARIABLES like group_concat_max_len 我们需要将这个值调大一点就可以解决上面这…
阅读更多...
利用 IDEA IDE 的轻量编辑模式快速查看和编辑工程外的文本文件

利用 IDEA IDE 的轻量编辑模式快速查看和编辑工程外的文本文件

作为程序员, 我们都知道 IDE 的很好用的, 它的文本编辑器功能也非常的强大, 用起来非常便捷. 在长年累月的使用中, 我们也变得对其非常熟悉, 以致于使用起其它简单地轻量级的文本编辑器来, 比如什么记事本, Notepad, UltraEdit 等等呀, 觉得既不方便又不熟悉. 关键是很多的操作…
阅读更多...
解决`idea`中`database`工具查询起别名乱码问题

解决`idea`中`database`工具查询起别名乱码问题

文章目录 解决idea中database工具查询起别名乱码问题场景复现如何解决方式一 设置编码方式二&#xff1a;修改字体 原因说明 解决idea中database工具查询起别名乱码问题 场景复现 使用Idea做查询的并且起别名出现了中文乱码 如何解决 方式一 设置编码 settings->输入框输…
阅读更多...
最新文章

Copyright @ 2022~2023