目录
- 一、队列的理解
- 二、Java中队列简述
-
- 2.1 Queue队列
- 2.2 双端队列
- 2.3 阻塞队列
- 2.4 非阻塞队列
- 三、各队列的区别与联系
一、队列的理解
队列是一种由数组和链表作为底层构造的只暴露头和尾操作API的数据结构,因此,队列是被认为是一种受限的数据结构。
队列的特性是:先进先出,类似于排队,原理如下图所示
二、Java中队列简述
队列Queue与Set和List同级,都继承了Collection,其次,双端队列接口Deque、阻塞队列BlockingQueue和非阻塞队列AvstractQueue实现了Queue接口,以下简述这三个类型的队列。
2.1 Queue队列
Queue是java中实现队列的接口,它总共只有6个方法,如下:
Queue的6个方法分类:
压入元素(添加):add()、offer()
相同:未超出容量,从队尾压入元素,返回压入的那个元素。
区别:在超出容量时,add()方法会对抛出异常,offer()返回false
弹出元素(删除):remove()、poll()
相同:容量大于0的时候,删除并返回队头被删除的那个元素。
区别:在容量为0的时候,remove()会抛出异常,poll()返回false
获取队头元素(不删除):element()、peek()
相同:容量大于0的时候,都返回队头元素。但是不删除。
区别:容量为0的时候,element()会抛出异常,peek()返回null。
引用资料:
https://blog.csdn.net/devnn/article/details/82591349
2.2 双端队列
deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。双端队列顾名思义就是队列的两个端口都能进出。
Deque的实现类是LinkedList,ArrayDeque,LinkedBlockingDeque,其中LinkedList是最常用的。值得注意的是,LinkedList也实现了List接口。
大多数Deque既可以是有容量限制也可以是无固定容量限制。
双端队列的插入、删除和检查方法各有两种形式,如下:
值得注意的是,插入操作要使用插入操作的特殊值形式,因为插入操作一般不允许失败。
由于双端队列的既能实现先进先出,也能实现先进后出,因此,双端队列一般有三种用途:
- 作为普通队列(先进先出)
Queue queue = new LinkedList()或Deque deque = new LinkedList()
- 作为堆栈(先进后出)
Deque deque = new LinkedList()
- 作为双端队列(两端可进出)
Deque deque = new LinkedList()
值得注意的是,Java堆栈Stack类已经过时,Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法:push()、pop()、peek()。
以下是双端队列从Queue接口继承方法的等效对比:
以下是双端队列与堆栈方法的等效方法对比:
文章中引用资料的链接:
https://blog.csdn.net/devnn/article/details/82716447
2.3 阻塞队列
1、理解
阻塞队列是一个支持两个附加操作的队列,即在队列为满时,存储元素的线程会等待队列可用,当队列为空时,获取元素的线程会等待队列为非空。
2、Java中的阻塞队列
阻塞队列接口有BlockingQueue和BlockingDeque两个,其中后者是双向队列。
其中BlockingQueue接口提供的方法如下:
BlockingDeque接口提供的方法如下:
头部元素:
尾部元素:
常见的阻塞队列有:
ArrayBlockingQueue : 一个由数组结构组成的有界阻塞队列。
LinkedBlockingQueue : 一个由链表结构组成的有界阻塞队列。
PriorityBlockingQueue : 一个支持优先级排序的无界阻塞队列。
DelayQueue: 一个使用优先级队列实现的无界阻塞队列。
SynchronousQueue: 一个不存储元素的阻塞队列。
LinkedTransferQueue: 一个由链表结构组成的无界阻塞队列。
LinkedBlockingDeque: 一个由链表结构组成的双向阻塞队列
具体的实现方法没有深究,有兴趣的可以看引用资料:
阻塞队列详解
2.4 非阻塞队列
1、理解
非阻塞队列不能阻塞,个人理解为普通队列,在多线程中,当队列满或空时,只能使用wait()和notify()进行队列消息传送。
2、Java中的非阻塞队列
AbstractQueue是非阻塞队列的接口,常见的非阻塞实现类有:
- LinkedList
- PriorityQueue
- ConcurrentLinkedQueue
(1)LinkedList
既实现了AbstractQueue接口也实现了Deque接口,也可作为双端队列使用。
(2)PriorityQueue
该类维护了一个有序队列,默认队头是规则排序中最小的元素,若多个最小值,则随机挑选。
排序的规则是通过构造函数comparator来实现,因此,该队列不允许插入null值或不可比较的对象。
(3)ConcurrentLinkedQueue
该类是基于链接点的线程安全队列,并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大小,ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢,需要遍历队列。此队列不允许使用null元素,
3、操作方法
add(E e):将元素 e 插入到队列末尾,如果插入成功,则返回 true;如果插入失败(即队列已满),则会抛出异常;
remove():移除队首元素,若移除成功,则返回 true;如果移除失败(队列为空),则会抛出异常;
remove(Object o):移除指定的元素,若移除成功,则返回 true;如果移除失败(队列为空),则会抛出异常
offer(E e):将元素 e 插入到队列末尾,如果插入成功,则返回 true;如果插入失败(即队列已满),则返回 false;
poll():移除并获取队首元素,若成功,则返回队首元素;否则返回 null;
peek():获取队首元素,若成功,则返回队首元素;否则返回 null
isEmpty():队列是否为空
size():队列长度
值得注意的是,一般情况下建议使用 offer、poll 和 peek 三个方法,不建议使用 add 和 remove 方法。因为使用 offer、poll 和 peek 三个方法可以通过返回值判断操作成功与否,而使用 add 和 remove 方法却不能达到这样的效果。
尤其对于插入操作,往往使用返回特殊值的方法。
引用资料:
https://blog.csdn.net/zyx1260168395/article/details/103656994
三、各队列的区别与联系
以下为个人理解,不正确请指正。
1、从数据的输入和输出角度来看,队列可以看成是普通和双端两种,普通队列是先进先出,而双端则可以两端进出。
2、从并发角度来看,队列可以看成阻塞和非阻塞两种,阻塞队列能实现阻塞,而非阻塞不能阻塞,阻塞和非阻塞队列都有普通队列和双端队列特性的实现类。