数据结构入门:队列

目录

文章目录

前言

1.队列

1.1 队列的概念及结构

 1.2 队列的实现

 1.2.1 队列的定义

1.2.2队列的初始化

 1.2.3 入队

 1.2.4 判空

 1.2.5 出队

 1.2.6 队头队尾数据

1.2.7 队列长度

1.2.8 队列销毁

总结


前言

        队列,作为一种重要的数据结构,在计算机科学中扮演着重要的角色,它按照先进先出(FIFO)的原则进行操作。它可以用来解决许多实际问题,队列的应用范围广泛,从操作系统中的进程调度,到网络中的数据传输,再到算法中的搜索和排序,队列无处不在。那么接下来,让我们一同开始这段关于队列的探索之旅吧!


1.队列

1.1 队列的概念及结构

 队列:

        只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特性。

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

 1.2 队列的实现

        队列的特性是先进先出,这里就要考虑选择顺序表还是链表来实现队列。队列需要大量的头删尾插的操作,顺序表进行头删的效率太低,所以这里我们选用链式结构来实现。

 1.2.1 队列的定义

 

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

         和定义链表的节点一样。但是也有所不同,我们知道队列需要大量的头删和尾插,为了方便尾插和头删我们最好再创建两个指针,一个指向头,另一个指向尾。那这样岂不是需要二级指针解决吗?

        这里我将会介绍一种新的方法来解决头删问题,前边我们已经知道对链表头进行操作方法有三种:

  • 一种是使用二级指针来达到修改头节点的目的
  • 另外一种是使用函数返回类型来达到修改的目的
  • 此外我们还可以使用带头结点的链表来解决对链表头操作时需要特殊处理的情况

         进行尾插操作时,需要传递头指针和尾指针,这样使用时函数的参数变多了,调用函数时也比较费劲,那这里我们不如直接再定义一个结构体来存放队列的头指针和尾指针,以及队列的长度。

typedef int Datatype;
typedef struct QueueNode
{struct QueueNode* next;Datatype data;}QueueNode;
typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Que;

        这样我们传参时就只需传第二个结构体就可以进行了。通过第二个结构体找到第一个结构体,然后进行一系列头删、尾插的操作,使用时实质和二级指针类似,它效果和带头节点的链表类似,只需要一级指针就可以解决。

        虽然栈和队列的逻辑非常简单,但是它们的结构却变得更加复杂了,链表和顺序表是后续数据结构学习的基础,一定要灵活掌握。

1.2.2队列的初始化

void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

        初始化就非常简单了,只需要将头指针和尾指针进行初始化置为NULL,长度置为0。这里我们也不需要创建新节点,由于我们就只要一个接口需要创建新节点(尾插),所以不需要封装成函数,对节点进行初始化。

我们在调用函数时也非常简单,将第二个结构体传过去:

Que q;//创建结构体变量QueueInit(&q);

 1.2.3 入队

void QueuePush(Que* pq, Datatype x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");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;}pq->size++;
}

         在入队操作时,我们需要创建新的节点,这里注意:创建新节点是为队列的节点申请空间,定义的第一个结构体才是队列节点的类型,所以新建节点是的类型也应该与第一个结构体对于,链表没有节点时,这时需要将头指针和尾指针指向新节点,进行特殊处理。后续再次入队就可以直接将新节点链接到尾节点的后边。入队新节点的同时注意将size++;记录队列长度。

 1.2.4 判空

入队之后就是出队,但考虑到后续多个接口中需要判空,这里就提前封装成一个函数

 

bool IsEmpty(Que* pq)
{assert(pq);return (pq->head == NULL);
}

 函数类型为bool类型,该类型返回值只有true(1)和false(0)两种,所以最后直接返回条件:pq->head == NULL如果为真就为true,假就为false。

 1.2.5 出队

void QueuePop(Que* pq)
{assert(pq);assert(!IsEmpty(pq));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;}pq->size--;
}

         出队需要先判断队列是否为NULL,然后将头指针向后移动(改变结构体指针),释放掉第一个节点,然后队列长度size--,但需要考虑一下特殊情况,就是删空的情况,如果只剩下一个节点就可以直接释放掉,然后将头指针和尾指针置为NULL。

 1.2.6 队头队尾数据

//队头
Datatype QueueFront(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq->head->data;
}
//队尾
Datatype QueueBlack(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq->tail->data;
}

         这里没什么好说的,直接返回队列头指针和尾指针指向节点的数据。但注意都需要进行判空操作。

1.2.7 队列长度

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

         直接返回队列的size即可。

1.2.8 队列销毁

 

void DestoryQueue(Que* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

         像链表一样,遍历队列一个一个的销毁节点,最后将指针置为NULL,队列长度size置为0。

        在链表学习以来部分同学会不会有这样的疑惑:销毁空间是不是不允许部分销毁吗?那一个一个节点的销毁不就可以部分销毁?那是因为标准C规定的是,释放空间时,一个malloc申请的空间必须全部释放,不可以将一个malloc申请的空间部分释放,而链表是每次增加节点就申请一次空间(malloc一次),每个节点都是相对独立的空间,所以需要一个个的遍历逐个销毁。


总结

        希望通过这篇博客,可以使你对队列有了更深入的了解,并能够应用这一概念解决实际问题。无论是在计算机科学中还是在日常生活中,队列都是一种重要的工具和思维方式,它能够帮助我们更好地组织和管理事务。最后,感谢阅读!      

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Web菜鸟教程 - Swagger实现自动生成文档

如果是一个人把啥都开发了,那用不到Swagger-UI,但一般情况是前后端分离的,所以就需要告诉前端开发人员都有哪些接口,传入什么参数,怎么调用,返回什么。有了Swagger-UI就能把这部分文档编写的业务给省去了。…

Android学习之路(2) 设置视图

一、设置视图宽高 ​ 在Android开发中,可以使用LayoutParams类来设置视图(View)的宽度和高度。LayoutParams是一个用于布局的参数类,用于指定视图在父容器中的位置和大小。 ​ 下面是设置视图宽度和高度的示例代码: …

[保研/考研机试] KY235 进制转换2 清华大学复试上机题 C++实现

题目链接&#xff1a; KY235 进制转换2 https://www.nowcoder.com/questionTerminal/ae4b3c4a968745618d65b866002bbd32 描述 将M进制的数X转换为N进制的数输出。 输入描述&#xff1a; 输入的第一行包括两个整数&#xff1a;M和N(2<M,N<36)。 下面的一行输入一个数…

面试攻略,Java 基础面试 100 问(十二)

如何将字符串转换为基本数据类型&#xff1f; 调用基本数据类型对应的包装类中的方法 parseXXX(String)或 valueOf(String)即可返回相应基本类型&#xff1b; 如何将基本数据类型转换为字符串&#xff1f; 一种方法是将基本数据类型与空字符串&#xff08;””&#xff09;连…

精挑细选的几个宝藏软件

是不是感觉你的电脑里面永远都缺少一款软件&#xff1f;每次想要使用某个功能的时候总是不能找到合适的&#xff0c;还要先去网上找&#xff0c;小编给大家分享几款超级实用的软件&#xff0c;建议低调收藏哦~ Proxyee-down/下载工具 proxyee-down是一款免费开源的http下载工…

聊聊看React和Vue的区别

Vue 更适合小项目&#xff0c;React 更适合大公司大项目&#xff1b; Vue 的学习成本较低&#xff0c;很容易上手&#xff0c;但项目质量不能保证...... 真的是这样吗&#xff1f;借助本篇文章&#xff0c;我们来从一些方面的比较来客观的去看这个问题。 论文档的丰富性 从两个…

hutool 导出复杂表头excel

假如已这样的表头导出数据 1.把包含表头的excel添加到项目资源目录 2.编写代码读取表头所在sheet,并且加入需导出的数据 /*** 导出excel*/public static void downloadExcel(List<List<Object>> list, HttpServletResponse response) throws IOException {/*Strin…

pc端与flutter通信失效, Method not found

报错情况描述&#xff1a;pc端与flutter通信&#xff0c;ios端能实现通信&#xff0c;安卓端通信报错 报错通信代码&#xff1a; //app消息通知window.callbackName function (res) {window?.jsBridge && window.jsBridge?.postMessage(JSON.stringify(res), "…

竞赛项目 深度学习的智能中文对话问答机器人

文章目录 0 简介1 项目架构2 项目的主要过程2.1 数据清洗、预处理2.2 分桶2.3 训练 3 项目的整体结构4 重要的API4.1 LSTM cells部分&#xff1a;4.2 损失函数&#xff1a;4.3 搭建seq2seq框架&#xff1a;4.4 测试部分&#xff1a;4.5 评价NLP测试效果&#xff1a;4.6 梯度截断…

arm:day2

.text 文本段 .global _start 声明一个_start全局函数的入口 _start: _start标签&#xff0c;就是c语言的函数/*mov r0,#9 r09mov r1,#15 r115cmp r0,r1 比较r0和r1beq stop 如果r0等于r1&#xff0c;跳转stopsubhi r0,r0,r1 如果r0大于r1&#xff0c;r0r0-r1su…

Spring Cloud构建微服务断路器介绍

什么是断路器 断路器模式源于Martin Fowler的Circuit Breaker一文。“断路器”本身是一种开关装置&#xff0c;用于在电路上保护线路过载&#xff0c;当线路中有电器发生短路时&#xff0c;“断路器”能够及时的切断故障电路&#xff0c;防止发生过载、发热、甚至起火等严重后果…

SpringBoot复习:(33)WebMvcAutoconfiguration内部静态类WebMvcAutoConfigurationAdapter

WebMvcAutoconfiguration内部静态类WebMvcAutoConfigurationAdapter实现了WebMvcConfigurer接口&#xff0c;重写了一些方法&#xff0c;也就是默认对Spring Mvc进行了一些配置: 该静态类上有个**Import**注解&#xff1a; Import(EnableWebMvcConfiguration.class) 它的父类…

全网最牛,Appium自动化测试框架-关键字驱动+数据驱动实战(二)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 util 包 util 包…

Git详解及使用

Git简介 Git 是一种分布式版本控制系统&#xff0c;它可以不受网络连接的限制&#xff0c;加上其它众多优点&#xff0c;目前已经成为程序开发人员做项目版本管理时的首选&#xff0c;非开发人员也可以用 Git 来做自己的文档版本管理工具。 大概是大二的时候开始接触和使用Gi…

FinOps 应用入门指南

入门指南介绍 什么是 FinOps &#xff1f; FinOps 是一种云成本管理和优化的解决方案&#xff0c;并为组织、企业、团队提供了系统化的方法论&#xff0c;其中每个人都应该对自己的云资源成本负责。 FinOps 是“Finance”和“DevOps”的合成词&#xff0c;强调业务团队和研发…

华为在ospf area 0单区域的情况下结合pbr对数据包的来回路径进行控制

配置思路&#xff1a; 两边去的包在R1上用mqc进行下一跳重定向 两边回程包在R4上用mqc进行下一跳重定向 最终让内网 192.168.10.0出去的数据包来回全走上面R-1-2-4 192.168.20.0出去的数据包来回全走 下面R1-3-4 R2和R3就是简单ospf配置和宣告&#xff0c;其它没有配置&#…

新手小白如何快速使用家用电脑远程访问摄像头【内网穿透】

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏:《高质量编程技巧》《cpolar》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 快速远程访问内网的摄像头前言具体操作步骤1. 打开“允许远程桌面”开关2. 建立TCP-IP隧道3. 获取生成的TCP-IP隧道…

PyQt5控件布局管理

Qt Designer提供了四种窗口布局&#xff1a;Vertical Layout(垂直布局) &#xff0c;Horizontal Layout(水平布局)&#xff0c;Grid Layout(栅格布局)&#xff0c;Form Layout(表单布局)&#xff0c;以及一种隐藏的布局—绝对布局 一般进行布局有两种方式&#xff1a; 一是通…

通达信接口调用过程需要借助什么?

通达信接口是一种用于获取、传输和处理股票市场相关数据的软件接口&#xff0c;以提供了一种连接股票市场数据源和数据使用者之间的通道&#xff0c;允许开发者通过编程方式获取股票行情数据、交易数据和相关信息等。如果调用通达信接口&#xff0c;需要借助以下几个方面的工具…