干货 | 45张图庖丁解牛18种Queue，你知道几种？

我们来看下节点类Node

private static class Node<E> {
    E item; //元素 Nodenext; //向后的节点链接 Nodeprev; //向前的节点链接 Node(Nodeprev, E element, Nodenext) { this.item = element; this.next = next; this.prev = prev;
    }
}

10.2 与ArrayList的区别

• 1.LinkedList的增加和删除效率相对较高，而查找和修改的效率相对较低。

• 2.以下情况建议使用ArrayList

• 频繁访问列表中的一个元素。
• 只在列表的首尾添加元素。

• 3.以下情况建议使用LinkedList

• 频繁地在列表开头、中间、末尾添加和删除元素。
• 需要通过循环迭代来访问列表中的元素。

10.3 LinkedList不是线程安全的

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

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

10.4 LinkedList的家庭成员关系

• LinkedList 继承了 AbstractSequentialList 类。

• LinkedList 实现了 Queue 接口，可作为队列使用。

• LinkedList 继承了 AbstractQueue抽象类，具有队列的功能。

• LinkedList 实现了 List 接口，可进行列表的相关操作。

• LinkedList 实现了 Deque 接口，可作为双向队列使用。

• LinkedList 实现了 Cloneable 接口，可实现克隆。

• LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

十一、并发安全ConcurrentLinkedQueue类

10.1 理解ConcurrentLinkedQueue

• ConcurrentLinked是由链表结构组成的线程安全的先进先出无界队列。
• 当多线程要共享访问集合时，ConcurrentLinkedQueue是一个比较好的选择。
• 不允许插入null元素
• 支持非阻塞地访问并发安全的队列，不会抛出ConcurrentModifiationException异常。
• size方法不是准确的，因为在统计集合的时候，队列可能正在添加元素，导致统计不准。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保证原子性（操作不可分割）
• 添加元素happen-before其他线程移除元素。
• 用法如下：

ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();
BuildingBlockWithName buildingBlock = new BuildingBlockWithName("三角形", "A");
concurrentLinkedQueue.add(buildingBlock);

10.2 ConcurrentLinkedQueue类继承了哪些类？

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

10.3 ConcurrentLinkedQueue类实现了哪些接口？

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

十二、双向数组ArrayDeque类

12.1 理解ArrayDeque

• 由数组组成的双端队列。
• 没有容量限制，根据需要扩容。
• 不是线程安全的。
• 禁止插入null元素。
• 当用作栈时，比栈速度快，当用作队列时，速度比LinkList快。
• 大部分方法的算法时间复杂度为O(1)。
• remove、removeFirstOccurrence、removeLastOccurrence、contains、remove 和批量操作的算法时间复杂度O(n)

12.2 使用方法

创建一个ArrayDeque，往arrayDeque队尾添加元素。

ArrayDeque arrayDeque = new ArrayDeque(); for (int i = 0; i < 50; i++) {
    arrayDeque.add(buildingBlock); // add方法等价于addLast方法 }

12.3 ArrayDeque实现了哪些接口

• Deque接口 - 可用于双端队列

十三、双向并发ConcurrentLinkedDeque类

13.1 理解ConcurrentLinkedDeque类

• 由链表结构组成的双向无界阻塞队列
• 插入、删除和访问操作可以并发进行，线程安全的类
• 不允许插入null元素
• 在并发场景下，计算队列的大小是不准确的，因为计算时，可能有元素加入队列。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保证原子性（操作不可分割）

13.2 ConcurrentLinkedDeque使用示例

创建两个积木：三角形、四边形，然后添加到队列：

BuildingBlockWithName buildingBlock1 = new BuildingBlockWithName("三角形", "A");
BuildingBlockWithName buildingBlock2 = new BuildingBlockWithName("四边形", "B");
ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();
concurrentLinkedDeque.addFirst(buildingBlock1);
concurrentLinkedDeque.addLast(buildingBlock2); //结果：顺序：三角形、四边形 

13.3 ConcurrentLinkedDeque实现了哪些接口

• Deque接口 - 可用于双端队列

十四、数组阻塞ArrayBlockingQueue类

14.1 理解ArrayBlockingQueue

• ArrayBlockingQueue是一个用数组实现的有界阻塞队列。
• 队列慢时插入操作被阻塞，队列空时，移除操作被阻塞。
• 按照先进先出（FIFO）原则对元素进行排序。
• 默认不保证线程公平的访问队列。
• 公平访问队列：按照阻塞的先后顺序访问队列，即先阻塞的线程先访问队列。
• 非公平性是对先等待的线程是非公平的，当队列可用时，阻塞的线程都可以争夺访问队列的资格。有可能先阻塞的线程最后才访问访问队列。
• 公平性会降低吞吐量。

14.2 ArrayBlockingQueue使用示例

创建两个积木：三角形、四边形，然后添加到队列：

BuildingBlockWithName buildingBlock1 = new BuildingBlockWithName("三角形", "A");
BuildingBlockWithName buildingBlock2 = new BuildingBlockWithName("四边形", "B");
ArrayBlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(100, true);
arrayBlockingQueue.add(buildingBlock1);
arrayBlockingQueue.add(buildingBlock2);

14.3 ArrayBlockQueue实现了哪些接口

• Deque接口 - 可用于双端队列

十五、链表阻塞LinkedBlockingQueue类

15.1 理解LinkedBlockingQueue

• LinkedBlockingQueue具有单链表和有界阻塞队列的功能。
• 队列慢时插入操作被阻塞，队列空时，移除操作被阻塞。
• 默认和最大长度为Integer.MAX_VALUE，相当于无界(值非常大：2^31-1)。

15.2 LinkedBlockingQueue使用示例

LinkedList linkedList1 = new LinkedList();
linkedList1.add("A");
linkedList1.add("B");
linkedList1.add("C");

15.3 LinkedBlockingQueue的应用场景

• 吞吐量通常要高于ArrayBlockingQueue。创建线程池时，参数runnableTaskQueue（任务队列），用于保存等待执行的任务的阻塞队列可以选择LinkedBlockingQueue。静态工厂方法Executors.newFixedThreadPool()使用了这个队列。

15.4 LinkedBlockingQueue实现了哪些接口

• LinkedBlockingQueue继承了 BlockingQueue类，可作为阻塞队列使用
• LinkedBlockingQueue继承了 AbstractQueue抽象类，具有队列的功能。
• LinkedBlockingQueue实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

十六、双向阻塞LinkedBlockingDeque类

16.1 理解LinkedBlockingDeque类

• 由链LinkedBlockingDeque = 阻塞队列+链表+双端访问
• 线程安全。
• 多线程同时入队时，因多了一端访问入口，所以减少了一半的竞争。
• 默认容量大小为Integer.MAX_VALUE。可指定容量大小。

16.2 LinkedBlockingDeque的应用场景

LinkedBlockingDeque可以用在“工作窃取“模式中。

工作窃取算法：某个线程比较空闲，从其他线程的工作队列中的队尾窃取任务来帮忙执行。

16.3 LinkedBlockingDeque实现了哪些接口

• LinkedBlockingDeque继承了 BlockingDeque类，可作为阻塞队列使用
• LinkedBlockingDeque继承了 AbstractQueue抽象类，具有队列的功能。
• LinkedBlockingDeque实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

十七、链表阻塞LinkedTransferQueue类

17.1 理解LinkedTransferQueue类

LinkedTransferQueue原理图

LinkedTransferQueue = 阻塞队列+链表结构+TransferQueue

之前我们讲“使命必达TransferQueue接口时已经介绍过了TransferQueue接口 ，所以LinkedTransferQueue接口跟它相似，只是加入了阻塞插入和移除的功能，以及结构是链表结构。

之前的TransferQueue也讲到了3个案例来说明TransferQueue的原理，大家可以回看TransferQueue。

17.2 LinkedTransferQueue接口比其他阻塞队列多了5个方法

• transfer(E e)
• tryTransfer(E e)
• tryTransfer(E e, long timeout, TimeUnit unit)
• getWaitingConsumerCount()
• hasWaitingConsumer()

17.3 LinkedTransferQueue代码示例

• 创建一个LinkedTransferQueue，生产者1 依次往队列中添加 A、B、C

生产者1 依次往队列中添加 A、B、C

• 生产者2 依次往队列中添加 D、E、F

生产者2 依次往队列中添加 D、E、F

• 消费者依次从队列首部开始消费元素，每次消费前，先sleep 2s，来演示transfer方法是否进行了等待。

消费者消费元素

• 运行结果

生产者1 transfer A 
生产者2 transfer D 2s后...
  
消费者      take A
生产者1 put B 2s后...
     
消费者      take D
生产者2 transfer E 2s后...
  
消费者      take B
生产者1 transfer C

• 代码执行结果分析

（1）首先生产者线程1和2 调用transfer方法来传输A和D，发现没有消费者线程接收，所以被阻塞。

（2）消费者线程过了2s后将A拿走了，然后生产者1 被释放继续执行，传输元素B，发现又没有消费者消费，所以进行了等待。

（3）消费者线程过了2s后，将排在队列首部的D元素拿走，生产者2继续往下执行，传输元素E，发现没有消费者，所以进行了等待。

（4）消费者线程过了2s后，将排在队列首部的B元素拿走，生产者1传输C元素，等待消费者拿走。

（5）消费者不再消费了，所以生产者1和生产者2都被阻塞了，元素C和，元素E都没有被拿走，而且生产者2的F元素还没有开始传输，因为在等待元素D被拿走。

（6）看下队列里面确实有C和E元素，而且E排在队列的首部。

队列里面的元素

17.4 LinkedTransferQueue实现了哪些接口

• LinkedBlockingDeque继承了 BlockingQeque类，可作为阻塞队列使用
• LinkedBlockingDeque继承了 AbstractQueue抽象类，具有队列的功能。

十八、传球好手SynchronousQueue类

18.1 理解SynchronousQueue类

SynchronousQueue原理图

• 我称SynchronousQueue为”传球好手“。想象一下这个场景：小明抱着一个篮球想传给小花，如果小花没有将球拿走，则小明是不能再拿其他球的。

• SynchronousQueue负责把生产者产生的数据传递给消费者线程。

• SynchronousQueue本身不存储数据，调用了put方法后，队列里面也是空的。

• 每一个put操作必须等待一个take操作完成，否则不能添加元素。

• 适合传递性场景。

• 性能高于ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

我们创建了两个线程，一个线程用于生产，一个线程用于消费

• 生产的线程依次put A、B、C三个值

生产的线程依次put A、B、C三个值

• 消费线程使用take来消费阻塞队列中的内容，每次消费前，等待5秒

消费线程每隔5s调用take方法

• 运行结果

t1     put A 
t2     take A 5秒后...

t1     put B 
t2     take B 5秒后...

t1     put C 
t2     take C

小结：说明生产线程执行put第一个元素"A" 操作后，需要等待消费者线程take完“A”后，才能继续往下执行代码。

18.1 SynchronousQueue应用场景

• 吞吐量通常要高于LinkedBlockingQueue。创建线程池时，参数runnableTaskQueue（任务队列），用于保存等待执行的任务的阻塞队列可以选择SynchronousQueue。静态工厂方法Executors.newCachedThreadPool()使用了这个队列

18.2 SynchronousQueue和LinkedTransferQueue的区别

• SynchronousQueue 不存储元素，而LinkedTransferQueue存储元素。
• SynchronousQueue 队列里面没有元素，而LinkedTransferQueue可以有多个存储在队列等待传输。
• LinkedTransferQueue还支持若传输不了，则丢到队列里面去。
• LinkedTransferQueue还支持若超过一定时间传输不了，则丢到队列里面去。

十九、优先级阻塞PriorityBlockingQueue类

19.1 理解PriorityBlockQueue类

PriorityBlockQueue的原理图

• PriorityBlockQueue = PriorityQueue + BlockingQueue
• 之前我们也讲到了PriorityQueue的原理，支持对元素排序。
• 元素默认自然排序。
• 可以自定义CompareTo()方法来指定元素排序规则。
• 可以通过构造函数构造参数Comparator来对元素进行排序。

19.2 PriorityBlockQueue实现了哪些接口

• LinkedBlockingQueue继承了 BlockingQueue接口，可作为阻塞队列使用
• LinkedBlockingQueue继承了 AbstractQueue抽象类，具有队列的功能。
• LinkedBlockingQueue实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

二十、延时阻塞DelayQueue类

20.1 理解DelayQueue

DelayQueue原理图

• DelayQueue = Delayed + BlockingQueue。队列中的元素必须实现Delayed接口。

public class DelayQueue<E extends Delayed> extends AbstractQueue<E> implements BlockingQueue<E> {

• 在创建元素时，可以指定多久可以从队列中获取到当前元素。只有在延时期满才能从队列中获取到当前元素。

20.2 源码解析

• 添加元素时，指定延时多久可以从队列中获取元素

public boolean offer(E e, long timeout, TimeUnit unit) { return offer(e);
}

• 获取元素的方法poll需要等待延时时间过了才能获取到元素

if (first == null || first.getDelay(NANOSECONDS) > 0) return null; else return q.poll();

poll方法

20.3 应用场景

• 缓存系统的设计：可以用DelayQueue保存缓存元素的有效期。然后用一个线程循环的查询DelayQueue队列，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。

• 定时任务调度：使用DelayQueue队列保存当天将会执行的任务和执行时间，一旦从DelayQueue中获取到任务就开始执行。比如Java中的TimerQueue就是使用DelayQueue实现的。

20.4 DelayQueue实现了哪些接口

• DelayQueue实现了 BlockingQueue接口，可作为阻塞队列使用

这一篇花了很多心思在上面，看官方英文文档、画原理图、写demo代码，排版。这恐怕是市面上最全最细讲解Queue的。