手撕数据结构—队列
队列
队列的话只允许在一端插入,在另外一端删除。插入数据的那一段叫做队尾,出数据的那一段叫做队头(从尾巴插入)。
因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的,因为栈的话就是说如果你入的过程当中边入边出的话,这个出的序列是不一样的。而对于队列来说没有这个影响。

如果要去模拟队列的话,用链式结构相对来说更加方便。我们就用单链表来模拟队列。因为我们到时候必须要进行尾插,因此我们也由此可以得知,到时候必须要得有一个尾指针。
对各种结构的简单比对与回顾总结
对于链表而言,不管是带不带哨兵位头结点,它的话仅仅只需要一个指针就够了。链表的话基本上几乎都只需要一个指针,单与双都一样,无非就是要么指向第一个节点(存有效数据),要么就是指向哨兵位头结点。
栈&顺序表
1. 原始状态:这两个的话都形式十分的相近,首先他们两个都必须得有一个类似于中枢控制系统的一个结构体,我们都知道这个结构体里面的话,他有三个成员:size,capacity,堆区指针。在一开始最开始,让我们创建完这个结构体类型之后,就会紧接着去创建这么一个结构体。(创建结构体类型+结构体变量)
2. 初始化:由于创建结构体的时候,是不能够对这个结构体进行初始化的,因此我们就有了初始化这个函数,把size与capacity的数据进行修改之后,我们还需要额外的去向内存的堆去申请一块空间,然后让堆区指针这个成员去指向这块从堆区申请过来的内存空间。 (初始化结构体变量的成员)
3. 传参说明:由于我这个结构体是在函数外面就已经创建好了。因此我传参的时候只需要穿结构体的地址(一级指针)。 (一级指针)
单链表
1. 原始状态:对于链表而言的话,仅仅只需要一个指针就已经可以了。一开始最开始就先创建一个结构体类型(是用来描述每一个节点的),然后再去创建一个该结构体指针phead,然后置空,防止成为野指针。 (创建结构体类型+链表头指针)
2. 初始化:如果是不带哨兵位头结点的,那么就根本没有必要去初始化,当有新的节点要插入进来的时候,别人自然自己会BuySLTNode (没有必要,节点push进来自己会BuySLTNode)
3. 参数说明:由于接下来各种各样的操作会改变这个phead所指向的位置,因此这个时候在函数内部传一级指针的话是没有任何意义的,因为形参的改变并不会影响实参,为了要真正能够改变phead的值/指向的位置,这个时候就需要传phead的地址,因此这边传参是二级指针。 (二级指针)
双向循环带头链表
1. 原始状态:因为不管怎么说,这还是一个链表嘛,当然首先还是得创建一个结构体,用来描述一下节点。然后再创建一个结构体指针phead并置空。 (创建结构体类型+链表头指针)
2. 初始化:由于这个链表是带哨兵位头结点的,因此有必要进行初始化这一步操作。初始化的内容也十分的简单,就去malloc一个哨兵位头结点,然后prev与next都指向自己就完事了。(BuyLTNode哨兵位头节点)
3. 参数说明:当我去进行初始化malloc一个哨兵位头结点的时候,虽然我也要去改动phead的指向位置(因为现在要指向这个哨兵位头结点了嘛),但是我可以让他返回malloc出来的哨兵位头结点地址,然后在函数外头把这个函数的返回结果赋给phead就OK,然后对于其他的函数各种操作,由于都是改变结构体的成员,因此只需要传入结构体的指针就可以,所以说这种情况的参数设置的话是一级指针。(一级指针)
队列
原始状态:(创建两个结构体类型+结构体变量)
初始化:(对结构体变量三个成员初始化)
参数说明:(结构体指针,即一级指针)
用单链表来模拟实现队列

队列的节点(结构体)创建与队列指针集合(结构体)创建
1. 首先我们是用单链表去模拟队列。因此首先我们得创建一个结构体,用来描述一个节点。
2. 但值得一提的是,由于是队列,尾部只能插入,头部只能弹出,因此我创建一个头指针置空后,我还是可以创建一个尾指针并置空,这个主要是为了方便之后我去进行尾插。然后多组数据的话最好放进一个结构里面。于是乎我们就再创建一个结构体,用来存头指针,尾指针,顺便维护一下队列中元素的个数。
3. 那为什么之前在单链表的时候不怎么干呢?主要原因在于意义不大,比如说我要进行尾删,你这样子有用吗?还是需要找前一个,反正都这么矬了,索性直接给一个头指针就完事了,但是在队列这边,该数据结构已经保证在队尾的话,数据只能进行插入,所以尾指针是有必要的。
typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QueueNode;
typedef struct Quene
{QueueNode* head;QueueNode* tail;int size;
}Queue;
队列的初始化
队列的初始化主要就是把指针集合的头指针与尾指针都变成空指针,然后此时此刻,由于队列当中没有元素,所以说size为0
void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
队列的销毁
并不说是任何东西都是在内存栈区上面,但比如说局部变量,函数栈帧这些东西确实是在内存的栈区上面,内存栈区里面的东西如果它一旦出了作用域,就会自动销毁,它所占的这个茅坑就会还给操作系统。
但是像链表当中的每一个节点都是在内存的堆区上面,内存堆积上面的东西是不会自动释放的,需要程序员去手动释放,如果不去释放的话,就永远占据在那,就会造成内存泄露。
显而易见,空队列也支持销毁。
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;QueueNode* next = NULL;while (cur != NULL){next = cur->next;free(cur);cur = next;}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
队列的队尾插入(入队)
在队列的队尾插入这一个操作当中,我们知道队列的话,它是用单链表来模拟,插入操作势必会涉及到节点的增加,对于单链表新增一个节点,这边的话并不重新分装成一个函数,而是直接在push函数里面malloc一下。
在这边的话还要尤其注意当队列中为空的这种特殊情况(也就是head与tail都为NULL)
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("QueuePush::Malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head != NULL){pq->tail->next = newnode;pq->tail = newnode;}else{pq->head = newnode;pq->tail = newnode;}pq->size++;
}
队列的队头弹出(出队)
如果说一个队列想要在队头弹出一个元素的话,首先必须得保证这个队列不是空的,如果说这个队列是空的话,那弹个毛线啊。
然后接下来还有一个特殊情况,当一个队列只有一个元素的时候,此时head与tail都是指向头结点,然后队头弹出把这个头结点给free了,此时此刻还需要额外处理一下tail,把它也变为NULL
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);QueueNode* newhead = pq->head->next;free(pq->head);pq->head = newhead;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}
队列的求元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
队列的判断是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
队列的返回队头元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->head->data;
}
队列的返回队尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->tail->data;
}
相关文章:

手撕数据结构—队列
队列队列的话只允许在一端插入,在另外一端删除。插入数据的那一段叫做队尾,出数据的那一段叫做队头(从尾巴插入)。因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的,因为栈的话就是说如…...

gdb调试工具和makemakefile工具
gdb调试工具和make/makefile工具 文章目录gdb调试工具和make/makefile工具一、gdb调试工具1.debug/release2.使用二、make/makefile1.什么是make/makefile2.编写一、gdb调试工具 1.debug/release 程序有两种默认的发布方式debug和release。release是无法进行调试的。Linux中g…...

【进阶数据结构】平衡搜索二叉树 —— AVL树
🌈感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树 博主水平有限,如有差错,欢迎斧正🙏感谢有你 码字不易,若有收获,期待你的点赞关注💙我们一起进步🚀 🌈我们上一篇…...
ROS使用(5)action学习
action消息的构建 首先进行功能包的创建 mkdir -p ros2_ws/src cd ros2_ws/src ros2 pkg create action_tutorials_interfaces action消息的类型 # Request --- # Result --- # Feedback 动作定义由三个消息定义组成,以---分隔。 从动作客户机向动作服务器发送…...
2023前端面试题集(含答案)之HTML+CSS篇(一)
在又到了金三银四的招聘季,不管你是刚入行的小白,亦或是混迹职场的老鸟,还在为面试前端工程师时不知道面试官要问什么怎么回答而苦恼吗?为了帮助你获得面试官的青睐,顺利通过面试,跳槽进入大厂,…...
设计模式2 - 观察者模式
定义: 观察者模式又叫发布订阅模式,它定义了对象之间的一对多依赖,这样一来,当一个对象改变状态时,它的所有依赖者都会收到通知并自动更新。 组成: Subject(通知者/被观察者)&#…...
ini配置文件
ini配置文件 ini文件是initialization file的缩写,即初始化文件,是widows系统配置文件所采用的存储格式。 文件扩展名: .ini ini配置文件的后缀名也不一定必须是.ini, 也可以是.cfg, .conf或者是.txt ini文件格式 ini配置文件由参数, 节, 注解组成 参…...
蓝桥杯备赛经验 pythonA组(非科班选手)
个人2022 CA组江苏省一等奖,决赛成绩不理想,没有拿到一二等奖,但是因为自己是非科班的学生,所以能拿到这样的成绩自己其实也应该知足了 题外话: 很多ACMer嘲笑蓝桥杯非常水,但是据我观察CA组决赛一等奖获奖…...

C++实现通讯录管理系统
通讯录是一个可以记录亲人、好友信息的工具,本博客借助黑马程序员的项目进行修改,利用C实现一个通讯录管理系统,旨在复习C的语法。 一、系统需求 系统需要实现的功能如下: 添加联系人∶向通讯录中添加新人,信息包括…...

开关电源Y电容放置的位置
Y电容,是我们工程师做开关电源设计时都要接触到的一个非常关键的元器件,它对EMI的贡献是相当的大的,但是它是一个较难把控的元器件,原理上并没有那么直观易懂,在EMI传播路径中需要联系到很多的寄生参数才能够去分析。 …...

二叉树的最小深度——递归法、迭代法
1题目给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例 1:输入:root [3,9,20,null,null,15,7]输出:2示例 2:输入&…...
Vue中常使用的三种刷新页面的方式
一、通过js原始方法刷新 缺点: 出现闪白 目录 一、通过js原始方法刷新 二、通过Vue自带的路由进行跳转 三、通过在APP页面进行demo进行刷新(推荐) 1.vue2写法 2. vue3.2写法 <template><div><div class"header"><button clic…...

【Shell】脚本
Shell脚本脚本格式第一个Shell脚本:hello.sh脚本常用执行方式1. bash或sh脚本的相对路径或绝对路径2. 输入脚本的绝对路径或相对路径3. 在脚本的路径前加上.或者source脚本格式 脚本以#!/bin/bash开头(指定解析器) #! 是一个约定的标记&…...
Mybatis的多表操作
1.Mybatis多表查询 1.1一对一查询 1.一对一查询的模型 用户表和订单表的关系为,一个用户有多个订单,一个订单只从属于一个用户 一对一查询的需求:查询一个订单,与此同时查询出该订单所属的用户2.创建Order和User实体public class…...
【JVM】字节码指令全解
文章目录 入门案例原始 java 代码编译后的字节码文件常量池载入运行时常量池方法字节码载入方法区main 线程开始运行,分配栈帧内存执行引擎开始执行字节码bipush 10istore_1ldc #3istore_2iload_1iload_2iaddistore_3getstatic #4iload_3invokevirtual #5return条件判断指令循…...

【精品】华为认证数通HCIA+HCIP题库分享(含答案解析)
嗨~大家好久不见,我是薄荷学姐,随着华为业务也全球领域的迅猛发展,越来越多人开始重视华为认证的重要性。今天给大家分享一下去年8月份的题库,基本都是一样,希望可以帮助到大家哈想要通过华为认证,除了进行…...
Qt cmake 资源文件的加载
Qt cmake 资源文件的加载概述qt_add_resourcesqt5_add_resourcesqt6_add_resources是否需要加载qrc文件需要加载qrc的情况不需要加载qrc的情况C 代码加载示例加载PNG加载CSS文件加载qrc文件Qt6相对于Qt5的一些变化Qt6和Qt5在加载资源文件方面的区别主要集中在两个方面ÿ…...

【链表OJ题(九)】环形链表延伸问题以及相关OJ题
环形链表OJ题 1. 环形链表 链接:141. 环形链表 描述: 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环&…...

【C++初阶】四、类和对象(下)
文章目录一、再谈构造函数构造函数体赋值初始化列表explicit关键字二、Static成员引入- 计算类中创建了多少个类对象概念特性静态成员函数的访问三、友元友元函数友元类四、内部类五、匿名对象六、拷贝对象时的一些编译器优化一、再谈构造函数 构造函数体赋值 在创建对象时&a…...

IDEA maven没有Import Maven projects automatically解决办法
去年装了个 IDEA2022版本 配置maven时我才发现是个大坑 他没有import Maven projects automatically配置项 当时看到我人都麻了 然后项目呢 用了依赖 这东西还不会自动下依赖 整的我那是相当难受 还在最后还是找到了解决办法 我们在配置文件上点击右键 然后鼠标选择如下图选项…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...

stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...