当前位置: 首页 > news >正文

手撕数据结构—队列

队列

  1. 队列的话只允许在一端插入,在另外一端删除。插入数据的那一段叫做队尾,出数据的那一段叫做队头(从尾巴插入)。

  1. 因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的,因为栈的话就是说如果你入的过程当中边入边出的话,这个出的序列是不一样的。而对于队列来说没有这个影响。

  1. 如果要去模拟队列的话,用链式结构相对来说更加方便。我们就用单链表来模拟队列。因为我们到时候必须要进行尾插,因此我们也由此可以得知,到时候必须要得有一个尾指针


对各种结构的简单比对与回顾总结

对于链表而言,不管是带不带哨兵位头结点,它的话仅仅只需要一个指针就够了。链表的话基本上几乎都只需要一个指针,单与双都一样,无非就是要么指向第一个节点(存有效数据),要么就是指向哨兵位头结点。

栈&顺序表

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. 原始状态:(创建两个结构体类型+结构体变量

  1. 初始化:(对结构体变量三个成员初始化

  1. 参数说明:(结构体指针,即一级指针


用单链表来模拟实现队列


队列的节点(结构体)创建与队列指针集合(结构体)创建

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;

队列的初始化

  1. 队列的初始化主要就是把指针集合的头指针与尾指针都变成空指针,然后此时此刻,由于队列当中没有元素,所以说size为0

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

队列的销毁

  1. 并不说是任何东西都是在内存栈区上面,但比如说局部变量,函数栈帧这些东西确实是在内存的栈区上面,内存栈区里面的东西如果它一旦出了作用域,就会自动销毁,它所占的这个茅坑就会还给操作系统。

  1. 但是像链表当中的每一个节点都是在内存的堆区上面,内存堆积上面的东西是不会自动释放的,需要程序员去手动释放,如果不去释放的话,就永远占据在那,就会造成内存泄露。

  1. 显而易见,空队列也支持销毁。

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

队列的队尾插入(入队)

  1. 在队列的队尾插入这一个操作当中,我们知道队列的话,它是用单链表来模拟,插入操作势必会涉及到节点的增加,对于单链表新增一个节点,这边的话并不重新分装成一个函数,而是直接在push函数里面malloc一下。

  1. 在这边的话还要尤其注意当队列中为空的这种特殊情况(也就是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++;
}

队列的队头弹出(出队)

  1. 如果说一个队列想要在队头弹出一个元素的话,首先必须得保证这个队列不是空的,如果说这个队列是空的话,那弹个毛线啊。

  1. 然后接下来还有一个特殊情况,当一个队列只有一个元素的时候,此时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原始方法刷新 缺点&#xff1a; 出现闪白 目录 一、通过js原始方法刷新 二、通过Vue自带的路由进行跳转 三、通过在APP页面进行demo进行刷新(推荐) 1.vue2写法 2. vue3.2写法 <template><div><div class"header"><button clic…...

【Shell】脚本

Shell脚本脚本格式第一个Shell脚本&#xff1a;hello.sh脚本常用执行方式1. bash或sh脚本的相对路径或绝对路径2. 输入脚本的绝对路径或相对路径3. 在脚本的路径前加上.或者source脚本格式 脚本以#!/bin/bash开头&#xff08;指定解析器&#xff09; #! 是一个约定的标记&…...

Mybatis的多表操作

1.Mybatis多表查询 1.1一对一查询 1.一对一查询的模型 用户表和订单表的关系为&#xff0c;一个用户有多个订单&#xff0c;一个订单只从属于一个用户 一对一查询的需求&#xff1a;查询一个订单&#xff0c;与此同时查询出该订单所属的用户2.创建Order和User实体public class…...

【JVM】字节码指令全解

文章目录 入门案例原始 java 代码编译后的字节码文件常量池载入运行时常量池方法字节码载入方法区main 线程开始运行,分配栈帧内存执行引擎开始执行字节码bipush 10istore_1ldc #3istore_2iload_1iload_2iaddistore_3getstatic #4iload_3invokevirtual #5return条件判断指令循…...

【精品】华为认证数通HCIA+HCIP题库分享(含答案解析)

嗨~大家好久不见&#xff0c;我是薄荷学姐&#xff0c;随着华为业务也全球领域的迅猛发展&#xff0c;越来越多人开始重视华为认证的重要性。今天给大家分享一下去年8月份的题库&#xff0c;基本都是一样&#xff0c;希望可以帮助到大家哈想要通过华为认证&#xff0c;除了进行…...

Qt cmake 资源文件的加载

Qt cmake 资源文件的加载概述qt_add_resourcesqt5_add_resourcesqt6_add_resources是否需要加载qrc文件需要加载qrc的情况不需要加载qrc的情况C 代码加载示例加载PNG加载CSS文件加载qrc文件Qt6相对于Qt5的一些变化Qt6和Qt5在加载资源文件方面的区别主要集中在两个方面&#xff…...

【链表OJ题(九)】环形链表延伸问题以及相关OJ题

环形链表OJ题 1. 环形链表 链接&#xff1a;141. 环形链表 描述&#xff1a; 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&…...

【C++初阶】四、类和对象(下)

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

IDEA maven没有Import Maven projects automatically解决办法

去年装了个 IDEA2022版本 配置maven时我才发现是个大坑 他没有import Maven projects automatically配置项 当时看到我人都麻了 然后项目呢 用了依赖 这东西还不会自动下依赖 整的我那是相当难受 还在最后还是找到了解决办法 我们在配置文件上点击右键 然后鼠标选择如下图选项…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...