轻松掌握数据结构——队列

第二章 队列

文章目录

• 第二章 队列
• 前言
• 一、队列是什么？
• 二、概念
• • 1.先进先出（First In First Out）
  • 2.入队列和出队列
• 三.队列的使用
• • 1.常用方法和功能
• 四.常用特殊队列
• • 1.循环队列
  • • （1）概念
    • （2）下标的计算
    • （3）循环队列判空判满的条件
  • 2.双端队列（Deque）
  • • （1）概念
    • （2）使用
• 五.这有几道题~
• 总结

前言

又见面啦！不知道大家那边最近有没有下雨啊？今早发现雨水渗进来，地上的书箱底儿都软了，搬起来时书从下面掉出，一看竟然是我第一本放进去的《你瞅啥》！ 怎么样，这正在“删除元素”的书箱像不像我们本期的主角——队列？（嘎，不像吗？请看下文！）没错，本期依旧会用最简答的例子来向大家介绍队列的概念和用法，轻松掌握！ 现在让我们开始吧~

一、队列是什么？

队列（Queue）是只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表。依旧和书箱一样，书只能从向上开口处放进去，也只能从箱子底漏出。 （漏了的箱子：QAQ）

二、概念

1.先进先出（First In First Out）

先进先出缩写是FIFO,这个在我们的选择题里面也经常出现，要记住哦~ 漏了的书箱，在放书时，我们先放一本《我的箱子》，再放一本《漏了！》，现在我们搬起书箱，大声念出来你会先后看到什么？！没错，先是《我的箱子》，然后又“啪——”的一声《漏了！》。 先放进去的会先掉出来，后放进去的后掉出来。 这，就是先进先出！ 图片上场~

请注意，这里队头指向第一个放入元素的位置，队尾指向最后可以插入元素的空位，不要搞混哦~

2.入队列和出队列

• ⼊队列：插入元素到队尾，进⾏插⼊操作的⼀端称为队尾（Tail/Rear）
• 出队列：删除队头元素，进⾏删除操作的⼀端称为队头（Head/Front）

以上就是队列的全部概念啦~ 怎么样，这是不是和破了的书箱一样？哈哈，现在让我们一起进入下一个环节——队列（Queue）的使用。

三.队列的使用

在Java中，Queue是个接口，不能被实例化，其底层是通过链表实现的。

Queue 这一行，主要是为了凸显一下我们今天的主角~

无奖竞猜：这串英文在本行以上出现过几次？结尾公布！

1.常用方法和功能

现在让我们狠狠地使用它们！ 注意：Queue是个接口，在实例化时需要实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(3);
q.offer(9);
q.offer(2);
q.offer(0); // 从队尾⼊队列
System.out.println(q.size());//5
System.out.println(q.peek()); // 获取队头元素 1
q.poll();//删除元素 1
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 3

if(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 个元素。

第二个公式推导：

OK，这个懂了，相信第一个也难不倒你！请大家根据同样的原理来推导一下第一个公式。

让我们进入下一个环节——

（3）循环队列判空判满的条件

结合前文出现的图不难发现，当队列为空的时候front和rear指向一处，所以

• 循环队列的判空条件： front == rear （so easy！）

那接下来，随着元素不断offer，当最后一个元素侵占rear的位置，无家可归的它该何去何从？嗯，没错

• 循环队列的判满条件：front == rear（有爱就有家版）

可问题来了，判空条件和判满条件一样的时候，怎么来区分才能防止溢出呢？   方法来啦~

• 判断空： return !isFull && front == rear;
• 判断满： return isFull;

嘿嘿，简单吧？其实还有一个办法可以让rear舒舒服服祝自己的房子！ 不知道大家有没有注意到在前面推导公式，介绍队列长度为N时，有一句“采用‘牺牲一个空位’的方式判空/判满”。 没错！另一个方法就是留一个空间。这样就能直接通过公式来判断下一个位置下标是否和front的相等判断了

判断满：front==(rear +1) % array.length;（重生之住上豪华单人大别野版）

好啦，方法就是这些，如果小伙伴们想到了别的办法，欢迎在评论区留言哦~ 现在有请另一位主角登场……大家不要走，我保证这是最后一个知识碎片 ！QAQ

2.双端队列（Deque）

（1）概念

双端队列（Deque）是指允许两端都可以进⾏⼊队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和⼊队，也可以从队尾出队和⼊队。 这里可以想象奶茶店的玻璃吸管，把它横过来，左右两端都可以放入一粒西米，左右倾斜两边都可以倒出西米（想喝果茶了）。

果茶……图片来也！

（2）使用

Deque也是⼀个接口，使用时必须创建LinkedList的对象

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

头部（队首）操作

• addFirst(e) / offerFirst(e) ：头部添加

• removeFirst() / pollFirst() ：头部删除

• getFirst() / peekFirst() ：获取头部

尾部（队尾）操作

• addLast(e) / offerLast(e) ：尾部添加

• removeLast() / pollLast() ：尾部删除

• getLast() / peekLast() ：获取尾部

简单嘛，这几个方法一看就会用。‘/’ 前面后面都一样用，双重选择，更贴心！ 可是‘/’前面后面真的没区别吗？上表格！（举例）

五.这有几道题~

1.用队列实现栈 2.用栈来实现队列 3.设计循环队列

总结

今天讲了很多，主要有队列的概念、用法、下标移动，还有两个特殊的常用队列的概念及其用法，奖励了自己…… 嗯，今天就到这里，祝大家好梦！

出现那串神秘字母的次数8哦~有找到吗？