队列（Queue）

队列（Queue）是计算机中的一种数据结构，保存在其中的数据具有“先进先出（FIFO，First In First Out）”的特性。

如果，你不明白“先进先出”是什么，试想下排队的场景，最先进来的人解决完问题后，最早离开—这就叫“先进先出”；

当队伍中有新来的人时，需要排在队伍的末端；而当队伍中有人解决完问题时，会从队伍的前端离开。

在队列中，我们管队伍的末端叫做“队尾”，管队伍的前端叫“队头”；新来的人，称之为“入队”。而离开的人，称之为“出队”；

稍有不同的是，在数据结构中，队列不支持从队伍的中间插入和离开，只能从头尾进行。而真实生活中，我们的队伍可没有这么和谐！！！！

还有一点是，当没有人在排队时，我们称之为“空队”，也就是队列为空的情况。

相关接口

Queue接口 - （单端）队列

Queue接口与List、Set同一级别，都是继承了Collection接口。

由于LinkedList实现了Deque接口，而Deque接口继承了Queue接口。自然地，LinkedList类也实现了Queue接口

public interface Queue<E> extends Collection<E> {
    //插入（抛出异常）
    boolean add(E e);
    //插入（返回特殊值）
    boolean offer(E e);
    //移除（抛出异常）
    E remove();
    //移除（返回特殊值）
    E poll();
    //检查（抛出异常）
    E element();
    //检查（返回特殊值）
    E peek();
}

Deque接口 - 双端队列（Double Ended Queue）

Deque，即双端队列（Double Ended Queue）。

Deque接口继承了Queue接口，即是双端队列，一个特殊的队列。

双端队列是指该队列两端的元素既能入队（offer）也能出队（poll）；如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈（push）和出栈（pop），遵循先进后出原则。

由于Deque接口继承Queue接口，当Deque当做队列（queue）使用时，只需要在头部删除，尾部添加即可。

除此之外，Deque也可以当做栈（stack）使用，这时入栈、出栈都在双端队列的头部进行。

public interface Deque<E> extends Queue<E> {
    // *** Deque methods ***
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
}

实现队列可以有很多种办法，例如，可以使用数组做存储，可以使用链表做存储。

Deque接口的实现类

非并发场景

对于非并发的情况，有两个Deque即可的实现类：

LinkedList 大小可变的链表双端队列，允许元素为 null；
ArrayDeque 大下可变的数组双端队列，不允许 null。

并发场景

在并发场景下，推荐使用LinkedBlockingDeque类，它是一个阻塞的双向队列。

BlockingQueue接口 - 阻塞队列

简而言之就是当队列满时，插入阻塞；当队列为空时，删除（取出）阻塞。常用于生产者和消费者场景。

ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。
LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。
PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。
DelayQueue：一个使用优先级队列实现的无界阻塞队列。
SynchronousQueue：一个不存储元素的阻塞队列。
LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

ArrayBlockingQueue

基于数组的阻塞队列实现，在ArrayBlockingQueue内部，维护了一个定长数组，以便缓存队列中的数据对象，其内部没有实现读写分离，长度是需要定义的，按照先进先出（FIFO）的原则对元素进行排序。是有界队列（bounded），在很多场合非常适合使用。默认情况下不保证线程公平的访问队列，所谓公平访问队列是指阻塞的线程，可以按照阻塞的先后顺序访问队列，即先阻塞线程先访问队列。非公平性是对先等待的线程是非公平的，当队列可用时，阻塞的线程都可以争夺访问队列的资格，有可能先阻塞的线程最后才访问队列。为了保证公平性，通常会降低吞吐量。

LinkedBlockingQueue

LinkedBlockingQueue 是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。

PriorityBlockingQueue

PriorityBlockingQueue是一个支持优先级的无界(unbounded)阻塞队列。默认情况下元素采取自然顺序升序排列。也可以自定义类实现compareTo()方法来指定元素排序规则，或者初始化PriorityBlockingQueue时，指定构造参数Comparator来对元素进行排序。需要注意的是不能保证同优先级元素的顺序。

DelayQueue

带有延迟时间的Queue，其中的元素只有当前指定的延迟时间到了，才能够从队列中获取该元素。DelayQueue中的元素必须实现Delayed接口，DelayQueue是一个无界队列，应用场景很多

PriorityQueue类（优先队列）

PriorityQueue类是Java 中优先队列的实现，队列元素在队列中的顺序，不是元素被加入队列的时间先后顺序，而是队列元素的大小。换句话说，最小的元素会永远排在这个队列的头部（即使这个元素是最后进入队列的）。

因此当调用peek()或pool()方法取出队列中头部的元素时，取出的是队列中的最小元素（而不是最早进入队列的元素）。

ArrayDeque类

ArrayDeque是Deque接口的具体实现类，底层使用数组来实现。

默认长度是16，根据添加的元素个数，动态扩容。

ArrayDeque是一个循环队列（circular queue）。它的实现比较高效，它的思路是这样：引入两个游标，head 和 tail，如果向队列里，插入一个元素，就把 tail 向后移动。如果从队列中删除一个元素，就把head向后移动。

我们看一下示意图：

如果向队列中插入D，那么，队列就会变成这样：

如果此时，从队列的头部把A删除，那只需要移动head指针即可：

通过这种方式，就可以使元素出队，入队的速度加快了。那如果 tail 已经指向了数组的最后一位怎么办呢？其实呀，只需要将tail重新指向数组的头就可以了。for example，tail已经指向数组最后一位了，再插入一个元素，就会变成这样：

使用这种方式，就可以循环使用一个数组来实现队列了。

Reference

Java集合–Queue队列介绍 - https://www.jianshu.com/p/b3676b3f2bb7
Java集合（七） Queue详解 - https://juejin.im/post/5a3763ed51882506a463b740#heading-4
BlockingQueue接口及其实现 - https://www.jianshu.com/p/0c87f39bc569

【Java】集合类 - Queue 接口