第二章 队列文章目录第二章 队列前言一、队列是什么二、概念1.先进先出First In First Out2.入队列和出队列三.队列的使用1.常用方法和功能四.常用特殊队列1.循环队列1概念2下标的计算3循环队列判空判满的条件2.双端队列Deque1概念2使用五.这有几道题~总结前言又见面啦不知道大家那边最近有没有下雨啊今早发现雨水渗进来地上的书箱底儿都软了搬起来时书从下面掉出一看竟然是我第一本放进去的《你瞅啥》怎么样这正在“删除元素”的书箱像不像我们本期的主角——队列嘎不像吗请看下文没错本期依旧会用最简答的例子来向大家介绍队列的概念和用法轻松掌握现在让我们开始吧~一、队列是什么队列Queue是只允许在⼀端进⾏插⼊数据操作在另⼀端进⾏删除数据操作的特殊线性表。依旧和书箱一样书只能从向上开口处放进去也只能从箱子底漏出。漏了的箱子QAQ二、概念1.先进先出First In First Out先进先出缩写是FIFO,这个在我们的选择题里面也经常出现要记住哦~漏了的书箱在放书时我们先放一本《我的箱子》再放一本《漏了》现在我们搬起书箱大声念出来你会先后看到什么没错先是《我的箱子》然后又“啪——”的一声《漏了》。先放进去的会先掉出来后放进去的后掉出来。这就是先进先出图片上场~请注意这里队头指向第一个放入元素的位置队尾指向最后可以插入元素的空位不要搞混哦~2.入队列和出队列⼊队列插入元素到队尾进⾏插⼊操作的⼀端称为队尾Tail/Rear出队列删除队头元素进⾏删除操作的⼀端称为队头Head/Front以上就是队列的全部概念啦~怎么样这是不是和破了的书箱一样哈哈现在让我们一起进入下一个环节——队列Queue的使用。三.队列的使用在Java中Queue是个接口不能被实例化其底层是通过链表实现的。Queue这一行主要是为了凸显一下我们今天的主角~无奖竞猜这串英文在本行以上出现过几次结尾公布1.常用方法和功能方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空现在让我们狠狠地使用它们注意Queue是个接口在实例化时需要实例化LinkedList的对象因为LinkedList实现了Queue接口。publicstaticvoidmain(String[]args){QueueIntegerqnewLinkedList();q.offer(1);q.offer(3);q.offer(9);q.offer(2);q.offer(0);// 从队尾⼊队列System.out.println(q.size());//5System.out.println(q.peek());// 获取队头元素 1q.poll();//删除元素 1System.out.println(q.poll());// 从队头出队列并将删除的元素返回 3if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());}}概念讲完了应用也举例了那么接下来结束……等一下不知道大家有没有想过如果队列不是漏底的箱子而是一根可伸缩的吸管他既可以竖着放变成队列也被弯成一个环还可以横着放……什么太啰嗦要走不不不要着急看到这里的你已经打败了99%的人马上就能提现了现在让我们欢迎循环队列和双端队列四.常用特殊队列1.循环队列1概念实际中我们有时还会使用一种队列叫循环队列。如生产者者消费者模型就会使用循环队列这个在选择题里经常看到。环形队列通常使⽤数组实现没错就是一个数组围成的圆圈结合下面图片更好理解哦~。当没有元素的时候队头front和队尾rear指向同一个位置。当我们放入一个元素的时候front位置不变rear指向下一个位置也就是下一个可以放入元素的空位。删除元素需要从队头删除也就是rear不变front位置设为null并向后移动一个位置2下标的计算这个简单由图可知当front往后时下标加一同样rear往前下标减……诶真的对吗大错特错试想一下当我一直重复入队出队操作front到达图片中位置5时加1下标为6可队列中并没有这个下标同理当rear在下表为0的位置时减1为-1这个下标可不大对劲——所以下标最后再往后(offset array.length): index (index offset) % array.length下标最前再往前(offset array.length): index (index array.length - offset) % array.length怎么样突然来上这么一大串是不是有点蒙嘿嘿我第一次看的时候也是。不过没关系现在我来为大家解释一下~队头 front 指向队头元素的位置。队尾 rear 指向队尾元素的下一个位置。队列长度为 N 采用“牺牲一个空位”的方式判空/判满因此最多存储 N-1 个元素。第二个公式推导当 rear front 时有效长度就是 rear - front 。当 rear front 时说明队列发生了“绕圈”直接相减会得到负数所以要加上 N 变成 rear - front N 。最后对 N 取模 % N 就能保证无论哪种情况结果都是 [0, N-1] 之间的有效长度。举例N % N 0N1 % N 1N2 % N 2OK这个懂了相信第一个也难不倒你请大家根据同样的原理来推导一下第一个公式。让我们进入下一个环节——3循环队列判空判满的条件结合前文出现的图不难发现当队列为空的时候front和rear指向一处所以循环队列的判空条件 front rear so easy那接下来随着元素不断offer当最后一个元素侵占rear的位置无家可归的它该何去何从嗯没错循环队列的判满条件front rear有爱就有家版可问题来了判空条件和判满条件一样的时候怎么来区分才能防止溢出呢方法来啦~通过添加 size 属性记录保留⼀个位置使用标记• 初始状态队列为空时front rear 0标志位 isFull false。• 每次⼊队检查rear是否与 front 重合如果重合设置 isFull true表⽰队列已满否则正常入队并移动 rear• 出队时移动 front 指针设置 isFull false判断空 return !isFull front rear;判断满 return isFull;嘿嘿简单吧其实还有一个办法可以让rear舒舒服服祝自己的房子不知道大家有没有注意到在前面推导公式介绍队列长度为N时有一句“采用‘牺牲一个空位’的方式判空/判满”。没错另一个方法就是留一个空间。这样就能直接通过公式来判断下一个位置下标是否和front的相等判断了判断满front(rear 1) % array.length;重生之住上豪华单人大别野版好啦方法就是这些如果小伙伴们想到了别的办法欢迎在评论区留言哦~现在有请另一位主角登场……大家不要走我保证这是最后一个知识碎片 QAQ2.双端队列Deque1概念双端队列Deque是指允许两端都可以进⾏⼊队和出队操作的队列deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和⼊队也可以从队尾出队和⼊队。这里可以想象奶茶店的玻璃吸管把它横过来左右两端都可以放入一粒西米左右倾斜两边都可以倒出西米想喝果茶了。果茶……图片来也2使用Deque也是⼀个接口使用时必须创建LinkedList的对象DequeIntegerstacknewArrayDeque();//双端队列的线性实现DequeIntegerqueuenewLinkedList();//双端队列的链式实现头部队首操作addFirst(e) / offerFirst(e) 头部添加removeFirst() / pollFirst() 头部删除getFirst() / peekFirst() 获取头部尾部队尾操作addLast(e) / offerLast(e) 尾部添加removeLast() / pollLast() 尾部删除getLast() / peekLast() 获取尾部简单嘛这几个方法一看就会用。‘/’ 前面后面都一样用双重选择更贴心可是‘/’前面后面真的没区别吗上表格举例抛异常版返回布尔/null版作用addFirstofferFirst头部添加addLastofferLast尾部添加五.这有几道题~1.用队列实现栈2.用栈来实现队列3.设计循环队列总结今天讲了很多主要有队列的概念、用法、下标移动还有两个特殊的常用队列的概念及其用法奖励了自己……嗯今天就到这里祝大家好梦出现那串神秘字母的次数8哦~有找到吗
企业数字化 ERP 产品动态
相关推荐
【轻松掌握数据结构】栈 第一章 栈 文章目录第一章 栈前言一、栈(Stack)是什么?二、概念1.后进先出(Last In First Out)2.压栈和出栈三.栈的使用1. 常用方法和功能2.栈的应用总结前言
本章会用最简单的话来讲什么是栈。本章附有代码ÿ… · 2026/10/26 5:44:53
Python程序打包实战:PyInstaller深度指南 1. Python程序打包的核心价值与场景打包Python程序是将.py源代码转换为可独立运行文件的过程,这解决了Python环境依赖的核心痛点。想象一下,你开发了一个数据分析工具,交给同事使用时对方却因为缺少numpy库而报错——这正是打包技术要解决的问… · 2026/11/19 5:06:31
iOS模拟器命令行高效操作指南 1. 项目概述作为一名iOS开发者,我每天都要和模拟器打交道。但直到三年前一次偶然的机会,我才发现原来通过命令行可以如此高效地操控模拟器。记得那天我正在调试一个需要频繁重启模拟器的项目,重复的GUI操作让我疲惫不堪。同事看我一脸烦躁&am… · 2026/11/18 23:42:18
福泉附近办电工证别踩坑!郑州报考避坑指南让你一次通过 福泉附近办电工证别踩坑!郑州报考避坑指南让你一次通过 你是不是正愁找不到电工证?马上就要上岗了,可证还没到手,机会都错过了。这年头, 特种作业证 几乎是很多蓝领岗位的硬门槛,特别是像 福泉附近… · 2026/11/19 5:05:37
福泉附近办电工证怎么报名?别被中介坑了,手把手教你避坑 福泉附近办电工证怎么报名?别被中介坑了,手把手教你避坑 你是不是也在福泉附近,听到有人在说“电工证”“低压电工证”“高压电工证”,但不知道怎么报名?怕被中介坑,怕走弯路,怕花了钱还拿不到证?别急,我来帮你理清楚,福泉附近办电工证怎么报名,到… · 2026/11/19 5:05:37
淮阳电工证怎么复审 全国通用电工证复审全攻略 淮阳电工证怎么复审 全国通用电工证复审全攻略 你手上攥着的这张【淮阳电工证】,可能是你找工作的“敲门砖”,甚至是改变你收入水平的关键。但别忘了,这证不复审,到期失效,等于白忙活一场。特别是像你在漯河从事房建工程的朋友,电工证不仅关系到岗位资… · 2026/11/19 5:05:37
电工作业操作许可证过期了怎么换证?含金量高到你想不到 电工作业操作许可证过期了怎么换证?含金量高到你想不到 证书过期了不知道怎么复审延期?别慌,这事儿真不是你一个人在扛。尤其是从事电工作业的朋友,电工作业操作许可证一旦过期,不仅影响工作,还可能面临罚款或停工。关键是,现在市场上证书种类繁多,很… · 2026/11/19 5:05:37
电工证年龄更改怎么操作?电子证书怎么查?别白交培训费! 电工证年龄更改怎么操作?电子证书怎么查?别白交培训费! 怕考不过白交培训费,尤其是像咱们河南市政公用工程从业者,年龄一改,报考资格、考试难度、甚至证书有效期都可能受影响。今天就来聊聊怎么操作【电工证年龄更改】,还有电子证书怎么查、怎么用,别… · 2026/11/19 5:05:37
你之前考的证在外省能不能转过来?栾城考电工证在哪报名良心建议 你之前考的证在外省能不能转过来?栾城考电工证在哪报名良心建议 之前考的证在外省能不能转过来?这几乎是每个想在栾城从事电工工作的人都会问的问题。特别是像你这样已经在外地考过证,现在想在栾城扎根的, 良心建议… · 2026/11/19 5:04:37
长春初级电工证怎么考?通过率揭秘全在这里 长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/18 8:19:55
国内电工证报考条件与考试时间 低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/18 8:19:53
电工作业时如何断电?电子证书到底能不能全国通用? 电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/18 14:38:14
姑苏区哪里考电工证好考前押题怎么找 姑苏区哪里考电工证好考前押题怎么找 工地太忙根本没时间复习考试,电工证考前还总找不到靠谱的 考前押题 资源,真让人头疼。如果你也是在苏州姑苏区从事建筑或电力行业的,那这些建议你一定要看完。 为什么姑苏区考电工证的人这么多?… · 2026/11/19 0:00:12
罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 之前考的证在外省能不能转过来?这几乎是每个特种作业证书持有者都会遇到的问题,特别是像你这样已经在外地工作多年,想回老家罗定发展或者重新规划职业路径的人。别急,今天就给你一条清晰的路… · 2026/11/19 0:00:12
罗定能考电工证吗 电工证含金量到底有多少? 罗定能考电工证吗 电工证含金量到底有多少? 之前考的证在外省能不能转过来,这几乎是每个准备考电工证的朋友最先想到的问题。特别是在罗定这样的地方,很多人的电工证都是在外地考的,现在想在当地继续使用,但不知道怎么办。实际上,电工证的 含金量… · 2026/11/19 0:00:12
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38