详解 18 种队列，你知道几种？

365次阅读  |  发布于3年以前

本篇主要内容如下：

本篇主要内容

帮你总结好的阻塞队列：

18种Queue总结

一、Queue自我介绍

队列原理图

1.1 Queue自我介绍

hi，大家好，我的英文名叫Queue，中文名叫队列，无论现实生活中还是计算机的世界中，我都是一个很重要的角色哦~

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

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

1.2 现实生活中的场景

1.3 计算机世界中的场景

二、高屋建瓴，纵览全局

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

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

18个Queue的继承实现关系图

注意：

三、万物归宗Queue接口

2.1 深入理解Queue接口的本质

2.2 Queue接口的核心方法

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

Queue的核心方法

动作 抛异常 返回特殊值
Insert add(e) offer(e)
Remove remove() poll
Examine element() peek()

四、双端可用Deque接口

4.1 深入理解Deque接口的原理

双端队列Deque

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

（2）Deque方法说明：

Deque方法

说明：

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

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

示例代码

4.1 哪些类实现了Deque接口

4.2 哪些类继承了Deque接口

五、队列骨架AbstractQueue抽象类

5.1 深入理解AbstractQueue抽象类

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

AbstractQueue的方法

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

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}
public E remove() {
    E x = poll();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}
public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

注意：

5.2 哪些类继承了AbstractQueue抽象类

六、阻塞缓冲BlockingQueue接口

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

阻塞队列满了的情况

阻塞队列为空的情况

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

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

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

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

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

6.2 案例解析

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

6.3 操刀BlockingQueue接口

BlockingQueue接口的10个核心方法：

继承的方法

10个核心方法总结如下：

BlockingQueue接口的10个核心方法

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

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

6.5 哪些类继承了BlockingQueue接口？

6.6 哪些类实现了BlockingQueue接口？

6.6 BlockingQueue接口继承了哪些接口

七、双端阻塞BlockingDeque接口

7.1 从原理图上理解BlockDeque

BlockingDeque满了

BlockQueue为空

7.2 BlockingDeque接口方法

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

BlockingDeque接口方法

示例：

尝试执行以下方法：

LinkedBlockingDeque queue = new LinkedBlockingDeque();
queue.addFirst("test1");
queue.addFirst(300);
queue.addLast("400");

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

300, test1, 400。

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

队列种的元素

7.3 BlockDeque和BlockQueue的对等方法

BlockDeque和BlockQueue的对等方法

7.4 BlockingDeque的特点

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

7.6 哪些类实现了BlockDeque接口？

八、使命必达TransferQueue接口

8.1 Transfer怎么理解？

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

8.2 生活中的案例

8.3 TransferQueue的原理解析

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

8.4 哪些类实现了TransferQueue接口？

九、优先由你PriorityQueue类

9.1 理解PriorityQueue类

本应该按照升序排序

按照自定义优先级排序

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

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

9.2 PriorityQueue类继承了哪些类？

9.2 PriorityQueue类实现了哪些接口？

十、双向链表LinkedList类

10.1 LinkedList的结构

LinkedList的结构

我们来看下节点类Node

private static class Node<E> {
    E item; //元素
    Node<E> next; //向后的节点链接
    Node<E> prev; //向前的节点链接

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

10.2 与ArrayList的区别

10.3 LinkedList不是线程安全的

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

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

10.4 LinkedList的家庭成员关系

十一、并发安全ConcurrentLinkedQueue类

10.1 理解ConcurrentLinkedQueue

ConcurrentLinkedQueue原理

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

10.2 ConcurrentLinkedQueue类继承了哪些类？

10.3 ConcurrentLinkedQueue类实现了哪些接口？

十二、双向数组ArrayDeque类

ArrayDeque原理图

12.1 理解ArrayDeque

12.2 使用方法

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

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

12.3 ArrayDeque实现了哪些接口

十三、双向并发ConcurrentLinkedDeque类

13.1 理解ConcurrentLinkedDeque类

ConcurrentLinkedDeque原理图

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实现了哪些接口

十四、数组阻塞ArrayBlockingQueue类

14.1 理解ArrayBlockingQueue

ArrayBlockingQueuey原理图

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实现了哪些接口

十五、链表阻塞LinkedBlockingQueue类

15.1 理解LinkedBlockingQueue

LinkedBlockingQueue原理

15.2 LinkedBlockingQueue使用示例

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

15.3 LinkedBlockingQueue的应用场景

15.4 LinkedBlockingQueue实现了哪些接口

十六、双向阻塞LinkedBlockingDeque类

16.1 理解LinkedBlockingDeque类

LinkedBlockingDeque原理图

16.2 LinkedBlockingDeque的应用场景

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

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

16.3 LinkedBlockingDeque实现了哪些接口

十七、链表阻塞LinkedTransferQueue类

17.1 理解LinkedTransferQueue类

LinkedTransferQueue原理图

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

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

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

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

17.3 LinkedTransferQueue代码示例

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

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

消费者消费元素

生产者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实现了哪些接口

十八、传球好手SynchronousQueue类

18.1 理解SynchronousQueue类

SynchronousQueue原理图

18.2 SynchronousQueue示例

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

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

消费线程每隔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应用场景

18.2 SynchronousQueue和LinkedTransferQueue的区别

十九、优先级阻塞PriorityBlockingQueue类

19.1 理解PriorityBlockQueue类

PriorityBlockQueue的原理图

19.2 PriorityBlockQueue实现了哪些接口

二十、延时阻塞DelayQueue类

20.1 理解DelayQueue

DelayQueue原理图

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);
}
if (first == null || first.getDelay(NANOSECONDS) > 0)
    return null;
else
    return q.poll();

poll方法

20.3 应用场景

20.4 DelayQueue实现了哪些接口

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

- END -

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8