设计循环队列(LeetCode)题目

news/2024/4/29 7:52:09/文章来源:https://blog.csdn.net/m0_73455775/article/details/129677458

这个也是力扣的题目,所以我们还是直接看

7dab41812b4840acaf14c2531000f890.png

100b21fe24514fe2b33cf6e01a78db9d.png 

请自己看题目

下面就看思路吧,首先是循环队列,我们想一下循环队列如何设计,用什么设计比较好一点,用顺序表还是链表

这里用链表看起来比较简单,因为他是循环的,所以尾节点可以直接连接到头节点就实现了循环队列,但是仔细想一下,前面malloc节点也是一个问题 ,并且malloc到一定的数量就不能再增加了,所以链表并不是一个很明智的选择

所以我们用顺序表实现,可是用顺序表如何实现?他的底层是连接的,那么如何实现循环?

所以我们可以实现逻辑循环就可以,我们可以看一下大概是这个样子

5b36187377b547b882f1f364bbb10956.png

 但是这样看起来并不好看,所以我们可以画成这样,看起来好看一点

dcbd41a174f147ab97a6286aedceb7c4.png

 就是这样,比较好看一点

我们将一下思路,我们可以malloc一个定长大小的空间,然后我们可以定义两个变量,一个front和rear(从名字也能看出来是啥意思),所以我们可以让rear往后走

5b4fc324579a490988e60faf6491c3bd.png

7c4667fced334d3daae0f0deaf0eb8c8.png 

827ae1f407ff4de0b0649de1ca90e0e3.png 

 但是这里的满和空的结果就是一样的了,所以无法判断满和空

所以我们可以多开一个空间,这样就是不一样了

661915927b8748c4918c6fd3d5eddd76.png

所以这样满的条件就是rear+1%(链表的长度) 是否等于front,如果等于的话就满了,如果没满的话就不等于

如果空的话就是rear等于front

就是这样,所以我们下面看一下实现

 1b3f62b0f72841308f64e69309c9456a.png

就是这样,里面的一个int类型的指针,还有就是rear和front,还有就是capacity这个是用来记录malloc了多少个数据的

下面在看一下

6b260523719849f1839d13e0c8ab63bb.png 

这里是和上一个题是一样的

下面在看一个

c55bae97e01443f2ae32a52a4cca090c.png 

看一下判断是否为空 和 是否为满,这个和我们前面说的思想是一样的,就是看是否 rear+1%(链表的长度) 是否等于front,如果等于的话就满了,如果没满的话就不等于

还有就是如果空的话就是rear等于front

就是这样

下面看一下Push

eb0c28af74dd434598922677b35cb67f.png

插入就是看是否为满,满了就返回false,否则就插入

4db49aa73cf3400ca586884d734ec970.png

我们看一下这个情况,如果是这样的话是可以继续插入的,但是这时候当他到了满了的时候,rear在++的话就超出范围了,所以我们需要在他++结束之后我们需要%一下capacity这就是为什么存他最大存储个数的原因了

所以我们就需要让他%capacity

然后在返回true

f93928f2250543bda5331880123153a4.png 

这个是删除,首先判断是否为空,为空的话就不能删除

下面就可以正常删除了,我们删除只需要++front就可以了,但是这里也是和Pop的时候是一样的front也可能会这样

eb593ebf6039468597fa61da47c05173.png 

如果是这样的话,front++也会超出最大范围,所以也需要%capacity

然后再返回true

 下面看一下取front的数据

f66e58ec035d4b3ba8a3a317790bcf31.png

这里如果为空的话就返回-1

如果不为空的话就返回这个位置的数据

下面在看一下取rear的数据

6e229ceb1184422fbc3be9ff8a5b95fa.png 

这里也是如果为空就返回-1

如果不为空,这里还是有两种情况,如果rear为0的话,这里就不能反悔rear -1位置的数据了,因为这里会变成负数,导致报错,所以这里是0的话就需要返回capacity位置的数据,如果他不是0的话就要正常返回rear-1位置的数据就可以了

下面看一下销毁

873a774cace84098bcb18fffed06d67f.png

这里就直接free他里面的a就可以了,然后把里面的其他数据置为0

结束

 

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

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

相关文章

干货|小白1分钟搞懂SRM管理系统

SRM管理系统是用来管理供应商,以及采购方和供应商进行采购交易的一套管理系统,在很多生产类企业中,往往是需要和ERP管理系统集成使用。原因:1.ERP管理系统无法实现采购商与供货商的有效协作;2.SRM管理系统对供应商的管…

Java分布式事务(七)

文章目录🔥Seata提供XA模式实现分布式事务_业务说明🔥Seata提供XA模式实现分布式事务_下载启动Seata服务🔥Seata提供XA模式实现分布式事务_搭建聚合父工程构建🔥Seata提供XA模式实现分布式事务_转账功能实现上🔥Seata提…

考研复试7 汇编语言、编程语言

一、寄存器 1. 寄存器概述 (1)典型的CPU包括器件 运算器控制器总线:内部总线实现CPU内部各个器件之间的联系;外部总线实现CPU和主板上其它器件的联系。 (2)8086CPU有14个寄存器,它们的名称为…

git查漏补缺之 stash

git查漏补缺之 stash Start 最近在工作的过程中,遇到 git 中的stash 暂存这个命令,感觉非常有用,写一个博客记录一下。 1. stash 首先第一个就是 stash ,英译过来的意思就是 存放/贮藏。 主要的使用场景: 我正在…

最好用的Markdown编辑器:MWeb Pro mac

MWeb pro Mac中文版是一款非常好用的Markdown编辑器和博客生成工具,支持语法高亮,预览,Fenced code blocks和代码高亮,Math ML支持,具有导出HTML/PDF,自定编辑器主题,字数统计,大纲视…

Linux--MySQL数据库的基本概念、编译安装以及MySQL数据库自动补全功能的实现

文章目录一.数据库的基本概念1、数据(Data)2、表3、数据库4、数据库管理系统(DBMS)5、数据库系统6、访问数据库的流程二.数据库系统发展史1、第一代数据库2、第二代数据库3、第三代数据库三、当今主流数据库介绍1、SQL Server (微…

电商出海:阿里、拼多多“快马扬鞭”

配图来自Canva可画 经过多年的发展,电商已经逐渐深入人们的日常生活中了,人们也愈发习惯使用电商平台了。得益于消费者需求的持续增长,电商行业的体量规模也在持续扩大,行业内也涌现出了诸多电商平台,比如淘宝、京东、…

error: C1083: 无法打开包括文件: “QtGui/QApplication”: No such file or directory

Qt系列文章目录 文章目录Qt系列文章目录前言一、原因二、解决办法1.修改pro工程文件2.在main.cpp中三、总结前言 当我们从网上或者从打开别人的工程师,报错,C1083: 无法打开包括文件: “QtGui/QApplication”。 原因:Qt5里不再用QtGui模块&a…

docker 安装 nginx无坑版

一. 拉取镜像 docker pull nginx二. 创建挂载目录 mkdir -p /usr/local/nginx/conf mkdir -p /usr/local/nginx/log mkdir -p /usr/local/nginx/html三. 从nginx容器里复制nginx的配置文件到主机里 创建个容器 docker run --name nginx -p 80:80 -d nginx将容器内的配置文件…

mysql之窗口函数练习

🍊今天复习一下mysql中的窗口函数,主要是通过几道练习题复习和加深一下对窗口函数的理解,对往期内容感兴趣的同学可以参考如下内容👇: 链接: 牛客SQL大厂真题——某音短视频.链接: 京东数据分析SQL面试题.链接: 百度用户增长SQL面…

Java实习生------MySQL10道面试题打卡

今日语录:“没有执行力,就没有竞争力 ”🌹 参考资料:图解MySQL、MySQL面试题 1、事务有哪些特性? 原子性: 一个事务中的所有操作,要么全部完成,要么全部不完成,不会出现…

Linux系统的安装以及参数配置 -- VMware(虚拟机)安装--ubuntu 20.04--VMware Tools工具安装

Linux系统的安装以及参数配置 PS:本文章为上课后整理笔记,作为以后学习工作的学习使用,也作为一次课程记录 一、Linux系统的安装常用方法 – 3种 1.直接Linux操作替换Windows – 专业Linux开发者 – 接受Linux相关软件的使用 2.安装双系统…

诗佛王维,眼前的苟且和远方的田野?

转自:媲美李白杜甫的诗人,他的人生可以复制_百科TA说 (baidu.com)他受到的羁绊,他做出的选择,提供了一种温润平和的过日子模式。大部分人无法决绝地脱离社会,隐遁起来,也无法在社会中不计底线,混…

JavaScript性能优化小窍门汇总(含实例)

在众多语言中,JavaScript已经占有重要的一席之地,利用JavaScript我们可以做很多事情 , 应用广泛。在web应用项目中,需要大量JavaScript的代码,将来也会越来越多。但是由于JavaScript是一个作为解释执行的语言&#xff…

Vue|样式绑定

class 与 style 是 HTML 元素的属性,用于设置元素的样式,我们可以用 v-bind 来设置样式属性。Vue.js v-bind 在处理 class 和 style 时, 专门增强了它。表达式的结果类型除了字符串之外,还可以是对象或数组。 文末名片获取源码 精…

根据平均分来划分等级-课后程序(JavaScript前端开发案例教程-黑马程序员编著-第2章-课后作业)

【案例2-1】 根据平均分来划分等级 一、案例描述 考核知识点 switch语句 练习目标 掌握switch语句的使用。 需求分析 switch语句也是多分支语句,针对某个表达式的值做出判断,来决定执行哪一段代码,本案例用于实现根据输入的小明同学的5门课…

百度CTO王海峰:全栈AI技术加持,打造新一代大语言模型文心一言

3月16日,百度在北京总部召开新闻发布会,百度创始人、董事长兼首席执行官李彦宏和百度首席技术官王海峰出席,李彦宏展示了新一代知识增强大语言模型文心一言在文学创作、商业文案创作、数理逻辑推算、中文理解、多模态生成五个使用场景中的综合…

【linux】管道pipe(),dup()系统调用

int pipe(int p[2]) 函数作用:生成一个管道,将管道读端的文件标识符存到p[0]中,将管道写端的文件标识符存到p[1]中。返回值:若成功返回0,失败返回-1 管道的理解 如图,当创建完管道以后的父进程fork出两个子…

Python中模块是个啥

昨天有粉丝问我说,啥是模块?经常听别人口中提这个词,但就是不懂。 模块可以认为是一盒主题积木,通过它可以拼出某一主题的东西。这与之前介绍的函数不同,一个函数相当于一块积木,而一个模块中可以包括很多函…

【C++进阶】unordered_set和unordered_map的介绍及使用

文章目录unordered系列容器介绍unordered_setunordered_set的模板参数unordered_set的函数接口介绍unordered_set的重要接口的使用构造函数增删查迭代器的使用unordered_mapunordered_map的模板参数unordered_map的函数接口介绍unordered_map的重要接口的使用增删查改迭代器的使…