第二章 队列文章目录第二章 队列前言一、队列是什么二、概念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哦~有找到吗