Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说只是给面试官讲了18种Java队列，竟然当场拿到offer！网友：牛批,希望能够帮助你!!!。

今日分享开始啦，请大家多多指教~

今天给大家介绍Queue队列，在计算机中是必不可少的角色。这是一种数据结构，大家可以把他想象成一个数组。给大家详细分享一下部分内容，篇幅比较长，大家需要耐心观看哦！

这次我们重点来看看Java中的Queue家族，总共涉及到18种Queue。

本篇主要内容如下：

一、Queue

队列原理图

1.1 Queue的介绍

有一个重要的朋友，他的英文名叫Queue，中文名叫队列，无论现实生活中还是计算机的世界中，都是一个很重要的角色。

它是一种数据结构，大家可以把他想象成一个数组，元素从它的一头进入、从另外一头出去，称为FIFO原则（先进先出原则）。

他还有两个亲兄弟：List（列表）、Set（集），他们都是Collection的儿子，他还有一个远房亲戚：Map（映射）。他们都是java.util包这个大家庭的成员哦！

1.2 现实生活中的场景

• 海底捞排号等位（先排号的优先进餐厅）
• 邮政员寄送信件（信箱是队列）

1.3 计算机世界中的场景

• 消息队列 RabbitMQ
• UDP协议（接收端将消息存放在队列中，从队列中读取数据）

二、高屋建瓴，纵览全局

18种队列分为三大类： 接口、抽象类、普通类。

弄清楚下面的继承实现关系对后面理解18种队列有很大帮助。

• Queue接口继承Collection接口，Collection接口继承Iterable接口。
• BlockingQueue接口、Deque接口继承Queue接口；
• AbstractQueue抽象类实现Queue接口；
• BlockingDeque接口、TransferQueue接口继承BlockingQueue接口；
• BlockingDeque接口继承Deque接口；
• LinkedBlockingDeque类实现BlockingDeque接口；
• LinkedTransferQueue类接口实现TransferQueue接口；
• LinkedList类、ArrayDeque类、ConcurrentLinkedDeque类实现了Deque接口；
• ArrayBlockingQueue类、LinkendBlockingQueue类、LinkedBlockingDeque类、LinkedTransferQueue类、SynchronousQueue类、PriorityBlockQueue类、DelayQueue类继承了AbstractQueue抽象类和实现了BlockingQueue接口；
• PriorityQueue类和ConcurrentLinkedQueue类继承了AbstractQueue抽象类；注意：
• Deque：全称Double-Ended queue，表示双端队列。
• 类实现接口，用implements
• 接口继承接口，用 extends
• 类继承类，用extends

三、万物归宗Queue接口

2.1 深入理解Queue接口的本质

• Queue接口是一种Collection，被设计用于处理之前临时保存在某处的元素。
• 除了基本的Collection操作之外，队列还提供了额外的插入、提取和检查操作。每一种操作都有两种形式：如果操作失败，则抛出一个异常；如果操作失败，则返回一个特殊值（null或false，取决于是什么操作）。
• 队列通常是以FIFO（先进先出）的方式排序元素，但是这不是必须的。
• 只有优先级队列可以根据提供的比较器对元素进行排序或者是采用正常的排序。无论怎么排序，队列的头将通过调用remove()或poll()方法进行移除。在FIFO队列中，所有新的元素被插入到队尾。其他种类的队列可能使用不同的布局来存放元素。
• 每个Queue必须指定排序属性。

2.2 Queue接口的核心方法

总共有3组方法，每一组方法对应两个方法。如下图所示：

Queue的核心方法

（1）比如添加（Insert）元素的动作，会有两种方式：add(e)和offer(e)。如果调用add(e)方法时，添加失败，则会抛异常，而如果调用的是offer(e)方法失败时，则会返回false。offer方法用于异常是正常的情况下使用，比如在有界队列中，优先使用offer方法。假如队列满了，不能添加元素，offer方法返回false，这样我们就知道是队列满了，而不是去handle运行时抛出的异常。

（2）同理，移除（Remove）元素的动作，队列为空时，remove方法抛异常，而poll返回null。如果移除头部的元素成功，则返回移除的元素。

（3）同理，检测（Examine）元素的动作，返回头部元素（最开始加入的元素），但不删除元素， 如果队列为空，则element()方法抛异常，而peek()返回false。

（4）Queue接口没有定义阻塞队列的方法，这些方法在BlockQueue接口中定义了。

（5）Queue实现类通常不允许插入null元素，尽管一些实现类比如LinkedList不禁止插入null，但是还是不建议插入null，因为null也被用在poll方法的特殊返回值，以说明队列不包含元素。

四、双端可用Deque接口

4.1 深入理解Deque接口的原理

双端队列Deque

（1）Deque概念： 支持两端元素插入和移除的线性集合。名称deque是双端队列的缩写，通常发音为deck。大多数实现Deque的类，对它们包含的元素的数量没有固定的限制的，支持有界和无界。

（2）Deque方法说明：

• 该列表包含包含访问deque两端元素的方法，提供了插入，移除和检查元素的方法。
• 这些方法中的每一种都存在两种形式：如果操作失败，则会抛出异常，另一种方法返回一个特殊值（null或false，取决于具体操作）。
• 插入操作的后一种形式专门设计用于容量限制的Deque实现，大多数实现中，插入操作不能失败，所以可以用插入操作的后一种形式。
• Deque接口扩展了Queue接口，当使用deque作为队列时，作为FIFO。元素将添加到deque的末尾，并从头开始删除。
• 作为FIFO时等价于Queue的方法如下表所示：

比如Queue的add方法和Deque的addLast方法等价。

• Deque也可以用作LIFO（后进先出）栈，这个接口优于传统的Stack类。当作为栈使用时，元素被push到deque队列的头，而pop也是从队列的头pop出来。
• Stack（栈）的方法正好等同于Deque的如下方法：

注意：peek方法不论是作为栈还是队列，都是从队列的检测队列的头，返回最先加入的元素。比如第一次put 100，第二次put 200，则peek返回的是100。如下图所示：

4.1 哪些类实现了Deque接口

• LinkedList类
• ArrayDeque类
• ConcurrentLinkedDeque类
• LinkedBlockingDeque类

4.2 哪些类继承了Deque接口

• BlockingDeque接口

五、队列骨架AbstractQueue抽象类

5.1 深入理解AbstractQueue抽象类

AbstractQueue是一个抽象类，继承了Queue接口，提供了一些Queue操作的骨架实现。

AbstractQueue的方法

方法add、remove、element方法基于offer、poll和peek。也就是说如果不能正常操作，则抛出异常。我们来看下AbstactQueue是怎么做到的。

• AbstractQueue的add方法

• AbstractQueue的remove方法

• AbstractQueue的element方法

注意：

• 如果继承AbstractQueue抽象类则必须保证offer方法不允许null值插入。

5.2 哪些类继承了AbstractQueue抽象类

• ArrayBlockingQueue类、LinkendBlockingQueue类、LinkedBlockingDeque类、 LinkedTransferQueue类、SynchronousQueue类、PriorityBlockQueue类、 DelayQueue类继承了AbstractQueue抽象类
• PriorityQueue类和ConcurrentLinkedQueue类继承了AbstractQueue抽象类

六、阻塞缓冲BlockingQueue接口

6.1 宏观来看BlockingQueue（阻塞队列）

• BlockQueue满了，PUT操作被阻塞

阻塞队列满了的情况

• BlockQueue为空，Take操作被阻塞

阻塞队列为空的情况

（1）BlockingQueue（阻塞队列）也是一种队列，支持阻塞的插入和移除方法。

（3）阻塞的插入：当队列满时，队列会阻塞插入元素的线程，直到队列不满。

（4）阻塞的移除：当队列为空，获取元素的线程会等待队列变为非空。

（5）应用场景：生产者和消费者，生产者线程向队列里添加元素，消费者线程从队列里移除元素，阻塞队列时获取和存放元素的容器。

（6）为什么要用阻塞队列：生产者生产和消费者消费的速率不一样，需要用队列来解决速率差问题，当队列满了或空的时候，则需要阻塞生产或消费动作来解决队列满或空的问题。

6.2 案例解析

线程A往阻塞队列（Blocking Queue）中添加元素，而线程B从阻塞队列中移除元素。

• 当阻塞队列为空的时候 （一个元素都没有），则从队列中获取元素的操作将会被阻塞。
• 生活中的案例：去海底捞吃火锅的时候，早上8点没人来吃火锅，所以需要等客人过来。
• 翻译成线程：现在没有元素需要添加，而且阻塞队列为空，所以线程B不需要从队列中拿元素出来，所以线程B获取元素的操作被阻塞了。
• 当阻塞队列满了的时候 （所有位置都放有元素），则从队列中添加元素的操作将会被阻塞。
• 生活中的案例：去海底捞吃火锅的时候，人太多了，需要排号，等其他桌空出来了才能进去。
• 翻译成线程：线程A往阻塞队列中添加元素，将队列填满了，线程B现在正在忙，无法拿出队列中的元素，所以阻塞队列没有地方再放元素了，这个时候线程A添加元素的操作就被阻塞了

6.3 操刀BlockingQueue接口

BlockingQueue接口的10个核心方法：

10个核心方法总结如下：

有三大类操作：插入、移除、检查。

• 插入有四种方法： add、offer、put、offer超时版。
• IllegalStateException - 队列满了
• ClassCastException - 添加的元素类型不匹配
• NullPointerException - 添加的元素为null
• IllegalArgumentException - 添加的元素某些属性不匹配
• add方法特别之处用于添加失败时抛出异常，共有四种异常：
• offer方法特别之处用于添加失败时只返回false
• put方法特别之处用于当阻塞队列满时，生产者如果往队列里put元素，则队列会一直阻塞生产者线程，直到队列可用或者响应中断退出
• offer超时方法特别之处用于当阻塞队列满时，生产者如果往队列里面插入元素，队列会阻塞生产者线程一段时间，如果超过了指定时间，生产者线程会退出，并返回false。
• 移除有四种方法： remove、poll、take、poll超时版
• NoSuchElementException - 如果这个队列是空的
• remove方法特别之处用于移除失败时抛出异常
• poll方法特别之处用于移除失败时返回null
• take方法特别之处用于当阻塞队列为空时，消费者线程如果从队列里面移除元素，则队列会一直阻塞消费者线程，直到队列不为空
• poll超时方法特别之处用于当阻塞队列空时，消费者如果从队列里面删除元素，则队列会一直阻塞消费者线程，如果超过了指定时间，消费者线程会退出，并返回null
• 检查有两种方法： element、peek
• element方法用于检测头部元素的存在性，如果队列为空，则抛出异常，否则返回头部元素。
• peek方法用于检测头部元素的存在性，如果队列为空，返回特殊值null，否则返回头部的元素。

6.4 BlockingQueue通过什么来阻塞插入和移除的？

• 当往队列里插入一个元素时，如果队列不可用，那么阻塞生产者主要通过LockSupport. park（this）来实现。
• park这个方法会阻塞当前线程，只有以下4种情况中的一种发生时，该方法才会返回。
• 与park对应的unpark执行或已经执行时。“已经执行”是指unpark先执行，然后再执行park的情况。
• 线程被中断时。
• 等待完time参数指定的毫秒数时。
• 异常现象发生时，这个异常现象没有任何原因。

6.5 哪些类继承了BlockingQueue接口？

• BlockingDeque接口 - 双端阻塞队列
• TransferQueue接口 - 传输队列

6.6 哪些类实现了BlockingQueue接口？

• ArrayBlockingQueue类 - 由数组构成的有界阻塞队列
• LinkedBlockingQueue类 - 由链表构成的有界阻塞队列，界限默认大小为Integer.MAX_Value（2^31-1），值非常大，相当于无界。
• LinkedBlockingDeque类 - 由链表构成的双向阻塞队列
• LinkedTransferQueue类 - 由链表构成的无界阻塞队列
• SynchronousQueue类 - 不存储元素的阻塞队列，只有一个元素进行数据传递。
• LinkedTransferQueue类 - 由链表构成的无界阻塞TransferQueue队列
• DelayQueue类 - 使用优先级队列实现的延迟无界阻塞队列

6.6 BlockingQueue接口继承了哪些接口

• BlockingQueue接口继承了Queue接口，可作为队列使用

七、双端阻塞BlockingDeque接口

7.1 从原理图上理解BlockDeque

• BlockQueue满了，两端的Take操作被阻塞

BlockingDeque满了

• BlockQueue为空，两端的Take操作被阻塞

BlockQueue为空

7.2 BlockingDeque接口方法

是阻塞队列BlockingQueue和双向队列Deque接口的结合。有如下方法：

最后队列中的元素顺序如下：

300, test1, 400。

先添加了test1放到队列的头部，然后在头部的前面放入300，所以300在最前面，成为头部，然后将400放入队列的尾部，所以最后的结果是300, test1, 400。

7.3 BlockDeque和BlockQueue的对等方法

7.4 BlockingDeque的特点

• 线程安全。
• 不允许使用null元素。
• 无界和有界都可以。

7.5 BlockingDeque接口继承了哪些接口？

• Queue接口，具有队列的功能
• Deque接口，具有双端队列的功能
• BlockingQueue接口，可作为阻塞队列使用

7.6 哪些类实现了BlockDeque接口？

• LinkedBlockingDeque

八、使命必达TransferQueue接口

8.1 Transfer怎么理解？

如果有消费者正在获取元素，则将队列中的元素传递给消费者。如果没有消费者，则等待消费者消费。我把它称作使命必达队列，必须将任务完成才能返回。

8.2 生活中的案例

• 针对TransferQueue的transfer方法
• 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。小明一次只能拿一个，快递员必须等小明拿了一个后，才能继续给第二个。
• 针对TransferQueue的tryTransfer方法
• 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。发现小明不在家，就把快递直接放到菜鸟驿站了。
• 针对TransferQueue的tryTransfer超时方法
• 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。发现小明不在家，于是先等了5分钟，发现小明还没有回来，就把快递直接放到菜鸟驿站了。

8.3 TransferQueue的原理解析

• transfer方法的原理
• 原理图解释：生产者线程Producer Thread尝试将元素B传给消费者线程，如果没有消费者线程，则将元素B放到尾节点。并且生产者线程等待元素B被消费。当元素B被消费后，生产者线程返回。
• 如果当前有消费者正在等待接收元素（消费者通过take方法或超时限制的poll方法时），transfer方法可以把生产者传入的元素立刻transfer（传输）给消费者。
• 如果没有消费者等待接收元素，transfer方法会将元素放在队列的tail（尾）节点，并等到该元素被消费者消费了才返回。
• tryTransfer(E e)
• 试探生产者传入的元素是否能直接传给消费者。
• 如果没有消费者等待接收元素，则返回false。
• 和transfer方法的区别是，无论消费者是否接收，方法立即返回。
• tryTransfer(E e, long timeout, TimeUnit unit)
• 带有时间限制的tryTransfer方法。
• 试图把生产者传入的元素直接传给消费者。
• 如果没有消费者消费该元素则等待指定的时间再返回。
• 如果超时了还没有消费元素，则返回false。
• 如果在超时时间内消费了元素，则返回true。
• getWaitingConsumerCount()
• 获取通过BlockingQueue.take()方法或超时限制poll方法等待接受元素的消费者数量。近似值。
• 返回等待接收元素的消费者数量。
• hasWaitingConsumer()
• 获取是否有通过BlockingQueue.tabke()方法或超时限制poll方法等待接受元素的消费者。
• 返回true则表示至少有一个等待消费者。

8.3 TransferQueue接口继承了哪些接口？

• BlockingQueue接口，可作为阻塞队列使用
• Queue接口，可作为队列使用

8.4 哪些类实现了TransferQueue接口？

• LinkedTranferQueue接口

九、优先由你PriorityQueue类

9.1 理解PriorityQueue类

• 本应该按照升序排序
  

• 按照倒序排序

按照自定义优先级排序

• PriorityQueue是一个支持优先级的无界阻塞队列。
• 默认自然顺序升序排序。
• 可以通过构造参数Comparator来对元素进行排序。

public PriorityQueue(Comparator<? super E> comparator) {
  this(DEFAULT_INITIAL_CAPACITY, comparator); 
}

• 自定义实现comapreTo()方法来指定元素排序规则。

public Comparator<? super E> comparator() {
  return comparator; 
}

• 不允许插入null元素。
• 实现PriorityQueue接口的类，不保证线程安全，除非是PriorityBlockingQueue。
• PriorityQueue的迭代器不能保证以任何特定顺序遍历元素，如果需要有序遍历，请考虑使用 Arrays.sort(pq.toArray)。
• 进列( offer、 add)和出列（ poll、 remove()）的时间复杂度O(log(n))。
• remove(Object) 和 contains(Object)的算法时间复杂度O(n)。
• peek、element、size的算法时间复杂度为O(1)。

9.2 PriorityQueue类继承了哪些类？

• AbstractQueue抽象类，具有队列的功能

9.2 PriorityQueue类实现了哪些接口？

• Queue接口，可作为队列使用。

十、双向链表LinkedList类

10.1 LinkedList的结构

• LinkedList实现了List和Deque接口，所以是一种双链表结构，可以当作堆栈、队列、双向队列使用。
• 一个双向列表的每一个元素都有三个整数值：元素、向后的节点链接、向前的节点链接

LinkedList的结构

我们来看下节点类Node

10.2 与ArrayList的区别

• 1.LinkedList的增加和删除效率相对较高，而查找和修改的效率相对较低。
• 2.以下情况建议使用ArrayList频繁访问列表中的一个元素。只在列表的首尾添加元素。
• 3.以下情况建议使用LinkedList频繁地在列表开头、中间、末尾添加和删除元素。需要通过循环迭代来访问列表中的元素。

10.3 LinkedList不是线程安全的

LinkedList不是线程安全的，所以可以使用如下方式保证线程安全。

List list = Collections.synchronizedList(new LinkedList<>());

小结

Java中的Queue家族，总共涉及到18种Queue，今天给大家分享的部分内容，其余部分明天再给大家分享哈~

今日份分享已结束，请大家多多包涵和指点！

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。