【校招VIP】Java中的常用队列- 校招VIP

转载声明：文章链接：https://blog.csdn.net/Archiea/article/details/122512483

一、队列的理解
队列是一种由数组和链表作为底层构造的只暴露头和尾操作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 方法却不能达到这样的效果。
尤其对于插入操作，往往使用返回特殊值的方法。
三、各队列的区别与联系
以下为个人理解，不正确请指正。
1、从数据的输入和输出角度来看，队列可以看成是普通和双端两种，普通队列是先进先出，而双端则可以两端进出。
2、从并发角度来看，队列可以看成阻塞和非阻塞两种，阻塞队列能实现阻塞，而非阻塞不能阻塞，阻塞和非阻塞队列都有普通队列和双端队列特性的实现类。