当前位置:首页 > Java技术 > Java 集合深入理解(9):Queue 队列

Java 集合深入理解(9):Queue 队列

2022年08月05日 22:18:50Java技术2

点击查看 Java 集合框架深入理解 系列, - ( ゜- ゜)つロ 乾杯~


今天心情不太好,来学一下 List 吧!

什么是队列

队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。

队列有两种:

  • 单队列
  • 循环队列

单队列就是常见的队列, 每次添加元素时,都是添加到队尾:

以数组实现的队列为例,初始时队列长度固定为 4,font 和 rear 均为 0:

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

每添加一个元素,rear 后移一位。当添加四个元素后, rear 到了索引为 4 的位置:

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

这时 a1,a2 出队,front 后移动到 2:

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

这时想要再添加两个元素,但 rear 后移两位后就会越界:

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

明明有三个空位,却只能再放入一个!这就是单队列的“假溢出”情况。

(上述参考借鉴自 http://www.nowamagic.net/librarys/veda/detail/2350

针对这种情况,解决办法就是后面满了,就再从头开始,也就是头尾相接的循环。这就是 “循环队列” 的概念。

循环队列:

循环队列中,
rear = (rear - size) % size

接着上面的例子,当 rear 大于 队列长度时,rear = ( 5 - 5) % 5 = 0 :

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

这样继续添加时,还可以添加几个元素:

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

那如何判断队列是否装满元素了呢,单使用 front == rear 无法判断究竟是空的还是满了。

两种方法:

  1. 加个标志 flag ,初始为 false,添加满了置为 true;
  2. 不以 front = rear 为放满标志,改为 (rear - front) % size = 1。

法 2 的公式放满元素时空余了一个位置,这个公式是什么意思呢?

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

接着上面的情况,当 rear 从后面添加元素跑到前面 0 时,再添加一个元素 a6,rear 后移一位到 1,这时 front = 2, (1 - 2) % 5 = 1, 满足放满条件。

因此,当 rear > font 时,队列中元素个数 = rear - font;

当 rear < font 时,队列中元素分为两部分: size - font 和 rear ,也就是 rear + size - font。以上述图片为例,队列中元素个数 = 1 + 5 - 2 = 4.

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

接着我们介绍 Java 集合框架中的队列 Queue

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

Java 集合中的 Queue 继承自 Collection 接口 ,Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。

Queue 用来存放 等待处理元素 的集合,这种场景一般用于缓冲、并发访问。

除了继承 Collection 接口的一些方法,Queue 还添加了额外的 添加、删除、查询操作。

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

添加、删除、查询这些个操作都提供了两种形式,其中一种在操作失败时直接抛出异常,而另一种则返回一个特殊的值:

Java 集合深入理解(9):Queue 队列 _ JavaClub全栈架构师技术笔记

Queue 方法介绍:

1.add(E), offer(E) 在尾部添加:

boolean add(E e);

boolean offer(E e);

他们的共同之处是建议实现类禁止添加 null 元素,否则会报空指针 NullPointerException;

不同之处在于 add() 方法在添加失败(比如队列已满)时会报 一些运行时错误 错;而 offer() 方法即使在添加失败时也不会奔溃,只会返回 false。

2016.11.21 添加

注意

Queue 是个接口,它提供的 add, offer 方法初衷是希望子类能够禁止添加元素为 null,这样可以避免在查询时返回 null 究竟是正确还是错误。

事实上大多数 Queue 的实现类的确响应了 Queue 接口的规定,比如 ArrayBlockingQueue,PriorityBlockingQueue 等等。

但还是有一些实现类没有这样要求,比如 LinkedList。

感谢 sumsear 指出。

2.remove(), poll() 删除并返回头部:

E remove();

E poll();

当队列为空时 remove() 方法会报 NoSuchElementException 错; 而 poll() 不会奔溃,只会返回 null。

3.element(), peek() 获取但不删除:

E element();

E peek();

当队列为空时 element() 抛出异常;peek() 不会奔溃,只会返回 null。

其他

1.虽然 LinkedList 没有禁止添加 null,但是一般情况下 Queue 的实现类都不允许添加 null 元素,为啥呢?因为 poll(), peek() 方法在异常的时候会返回 null,你添加了 null 以后,当获取时不好分辨究竟是否正确返回。

2.Queue 一般都是 FIFO 的,但是也有例外,比如优先队列 priority queue(它的顺序是根据自然排序或者自定义 comparator 的);再比如 LIFO 的队列(跟栈一样,后来进去的先出去)。

不论进入、出去的先后顺序是怎样的,使用 remove(),poll() 方法操作的都是 头部 的元素;而插入的位置则不一定是在队尾了,不同的 queue 会有不同的插入逻辑。

Thanks

https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

http://www.nowamagic.net/librarys/veda/detail/2350

http://www.nowamagic.net/librarys/veda/detail/2351

作者:拭心
来源链接:https://blog.csdn.net/u011240877/article/details/52860924

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/java/18045.html

标签: Java集合Java
分享给朋友:

“Java 集合深入理解(9):Queue 队列” 的相关文章

Java空指针异常解决java.lang.NullPointerException解决心得

Java空指针异常解决java.lang.NullPointerException解决心得

今天做课设的时候运行程序报出以下错误 java.lang.NullPointerException 首先要理解的是此错误并不会在 程序中报错,只会在运行的时候报错。 是由于某个参数(集合,数组等数据)可能出现一个null值而导致后面的程序不能运行时...

一分钟搞定Java环境变量配置

一分钟搞定Java环境变量配置

对于学Java的人来说,成功配置环境变量是第一步,因为后期不论 你做什么工作,会发现都需要这些,接下来介绍如何安装与配置,我按照jdk1.6来说明,其他一致。 下载官网 首先将jdk安装好后进行配置。 右击“计算机”,右键打开“属性”,...

两年前写的Java基础总结书

两年前写的Java基础总结书

想法衍生 两年前的我,突发奇想,把自己学的Java基础进行规范化的整理,因为自己的文档编辑能力有限,所以写的排版不是很好,参照图书排版的形式,将书籍进行整理,可以供学习Java基础的朋友参考,由于时间有限,可能也会有问题,请指出。下载地址在最后 截图如下:...

Java实现Email发送

一、前言最近将项目的登录密码从图形验证码改为了短信验证码,同时也将忘记密码时长度进行了修改,在修改时,想到了之前在一些国外的网站上,使用过邮箱接收验证码的情况,故想到何妨不自己尝试整合一下Java程序发送邮件信息呢,所以动手整合了Email的发送实例。二、Email发送协议想要在互联网上提供电子邮件...

Java中四种访问修饰符的区别

在java中共有4种访问级别,按访问权限由高到低为:public(公有的)、protected(受保护的)、友好的(没有任何访问权限关键字修饰)和private(私有的)。 类型 类内部 同一个包其...

深入理解 Java 并发锁

深入理解 Java 并发锁

📦 本文以及示例源码已归档在 javacore 一、并发锁简介 确保线程安全最常见的做法是利用锁机制(Lock、sychronized)来对共享数据做互斥同步,这样在同一个时刻,只有一个线程可以执行某个方法或者某个代码块,那么操作必然是原子性的,线程安全的...

Java 并发核心机制

Java 并发核心机制

📦 本文以及示例源码已归档在 javacore 一、J.U.C 简介 Java 的 java.util.concurrent 包(简称 J.U.C)中提供了大量并发工具类,是 Java 并发能力的主要体现(注意,不是全部,有部分并发能力的支持在其他包中)。...

Java 内存模型

Java 内存模型

📦 本文以及示例源码已归档在 javacore Java 内存模型(Java Memory Model),简称 JMM。 JVM 中试图定义一种 JMM 来屏蔽各种硬件和操作系统的内存访问差异,以实现让 Java 程序在各种平台下都能达到一致的内存访问效果。...

Java 日志框架详解

Java 日志框架详解

1. JUL学习 JUL全称Java util Logging是java原生的日志框架,使用时不需要另外引用第三方类库,相对其他日志框 架使用方便,学习简单,能够在小型应用中灵活使用。 1.1 架构介绍 Loggers...

JDBC连接时所犯错误1.字符集设置不合适2.连接MySQL8.0社区版时时区不一致3..包名不能以Java.命名4.驱动被弃用

Microsoft JDBC Driver 的主页为:https://msdn.microsoft.com/en-us/data/aa937724.aspx 下载所需驱动 今天连接时报了四次错,记录下来 1.java.sql.SQLException:...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。