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

今天给大家介绍 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 - 添加的元素为 nullIllegalArgumentException - 添加的元素某些属性不匹配 add 方法特别之处用于添加失败时抛出异常，共有四种异常：offer 方法特别之处用于添加失败时只返回 falseput 方法特别之处用于当阻塞队列满时，生产者如果往队列里 put 元素，则队列会一直阻塞生产者线程，直到队列可用或者响应中断退出 offer 超时方法特别之处用于当阻塞队列满时，生产者如果往队列里面插入元素，队列会阻塞生产者线程一段时间，如果超过了指定时间，生产者线程会退出，并返回 false。

• 移除有四种方法： remove、poll、take、poll 超时版 NoSuchElementException - 如果这个队列是空的 remove 方法特别之处用于移除失败时抛出异常 poll 方法特别之处用于移除失败时返回 nulltake 方法特别之处用于当阻塞队列为空时，消费者线程如果从队列里面移除元素，则队列会一直阻塞消费者线程，直到队列不为空 poll 超时方法特别之处用于当阻塞队列空时，消费者如果从队列里面删除元素，则队列会一直阻塞消费者线程，如果超过了指定时间，消费者线程会退出，并返回 null

• 检查有两种方法： element、peekelement 方法用于检测头部元素的存在性，如果队列为空，则抛出异常，否则返回头部元素。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，今天给大家分享的部分内容，其余部分明天再给大家分享哈~

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