[转]说说Queue

2019-06-17 本文已影响0人瑜小贤

1、简介

Queue（队列）：一种特殊的线性表，它只允许在表的前端（front）进行删除操作，只允许在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。

每个元素总是从队列的rear端进入队列，然后等待该元素之前的所有元素出队之后，当前元素才能出对，遵循先进先出（FIFO）原则。

下面是Queue类的继承关系图：

queue

图中我们可以看到，最上层是Collection接口，Queue满足集合类的所有方法：

add(E e)：增加元素；
remove(Object o)：删除元素；
clear()：清除集合中所有元素；
size()：集合元素的大小；
isEmpty()：集合是否没有元素；
contains(Object o)：集合是否包含元素o。

2、队列

2.1、Queue

Queue：队列的上层接口，提供了插入、删除、获取元素这3种类型的方法，而且对每一种类型都提供了两种方式，先来看看插入方法：

add(E e)：插入元素到队尾，插入成功返回true，没有可用空间抛出异常 IllegalStateException。
offer(E e)：插入元素到队尾，插入成功返回true，否则返回false。

add和offer作为插入方法的唯一不同就在于队列满了之后的处理方式。add抛出异常，而offer返回false。

再来看看删除和获取元素方法（和插入方法类似）：

remove()：获取并移除队首的元素，该方法和poll方法的不同之处在于，如果队列为空该方法会抛出异常，而poll不会。
poll()：获取并移除队首的元素，如果队列为空，返回null。
element()：获取队列首的元素，该方法和peek方法的不同之处在于，如果队列为空该方法会抛出异常，而peek不会。
peek()：获取队列首的元素，如果队列为空，返回null。

如果队列是空，remove和element方法会抛出异常，而poll和peek返回null。

当然，Queue只是单向队列，为了提供更强大的功能，JDK在1.6的时候新增了一个双向队列Deque，用来实现更灵活的队列操作。

2.2、Deque

Deque在Queue的基础上，增加了以下几个方法：

addFirst(E e)：在前端插入元素，异常处理和add一样；
addLast(E e)：在后端插入元素，和add一样的效果；
offerFirst(E e)：在前端插入元素，异常处理和offer一样；
offerLast(E e)：在后端插入元素，和offer一样的效果；
removeFirst()：移除前端的一个元素，异常处理和remove一样；
removeLast()：移除后端的一个元素，和remove一样的效果；
pollFirst()：移除前端的一个元素，和poll一样的效果；
pollLast()：移除后端的一个元素，异常处理和poll一样；
getFirst()：获取前端的一个元素，和element一样的效果；
getLast()：获取后端的一个元素，异常处理和element一样；
peekFirst()：获取前端的一个元素，和peek一样的效果；
peekLast()：获取后端的一个元素，异常处理和peek一样；
removeFirstOccurrence(Object o)：从前端开始移除第一个是o的元素；
removeLastOccurrence(Object o)：从后端开始移除第一个是o的元素；
push(E e)：和addFirst一样的效果；
pop()：和removeFirst一样的效果。

可以发现，其实很多方法的效果都是一样的，只不过名字不同。比如Deque为了实现Stack的语义，定义了push和pop两个方法。

3、阻塞队列

3.1、BlockingQueue

BlockingQueue（阻塞队列），在Queue的基础上实现了阻塞等待的功能。它是JDK 1.5中加入的接口，它是指这样的一个队列：当生产者向队列添加元素但队列已满时，生产者会被阻塞；当消费者从队列移除元素但队列为空时，消费者会被阻塞。

先给出BlockingQueue新增的方法：

put(E e)：向队尾插入元素。如果队列满了，阻塞等待，直到被中断为止。
boolean offer(E e, long timeout, TimeUnit unit)：向队尾插入元素。如果队列满了，阻塞等待timeout个时长，如果到了超时时间还没有空间，抛弃该元素。
take()：获取并移除队首的元素。如果队列为空，阻塞等待，直到被中断为止。
poll(long timeout, TimeUnit unit)：获取并移除队首的元素。如果队列为空，阻塞等待timeout个时长，如果到了超时时间还没有元素，则返回null。
remainingCapacity()：返回在无阻塞的理想情况下（不存在内存或资源约束）此队列能接受的元素数量，如果该队列是无界队列，返回Integer.MAX_VALUE。
drainTo(Collection<? super E> c)：移除此队列中所有可用的元素，并将它们添加到给定 collection 中。
drainTo(Collection<? super E> c, int maxElements)：最多从此队列中移除给定数量的可用元素，并将这些元素添加到给定 collection 中。

BlockingQueue最重要的也就是关于阻塞等待的几个方法，而这几个方法正好可以用来实现生产-消费的模型。

从图中我们可以知道实现了BlockingQueue的类有以下几个：

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

ArrayBlockingQueue

ArrayBlockingQueue是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不保证访问者公平的访问队列，所谓公平访问队列是指阻塞的所有生产者线程或消费者线程，当队列可用时，可以按照阻塞的先后顺序访问队列，即先阻塞的生产者线程，可以先往队列里插入元素，先阻塞的消费者线程，可以先从队列里获取元素。通常情况下为了保证公平性会降低吞吐量。我们可以使用以下代码创建一个公平的阻塞队列：

ArrayBlockingQueue fairQueue = new  ArrayBlockingQueue(1000, true);

访问者的公平性是使用可重入锁实现的，代码如下：

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}

LinkedBlockingQueue

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

PriorityBlockingQueue

PriorityBlockingQueue是一个支持优先级的无界队列。默认情况下元素采取自然顺序排列，也可以通过比较器comparator来指定元素的排序规则。元素按照升序排列。

SynchronousQueue

SynchronousQueue是一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作，否则不能继续添加元素。SynchronousQueue可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素，非常适合于传递性场景,比如在一个线程中使用的数据，传递给另外一个线程使用，SynchronousQueue的吞吐量高于LinkedBlockingQueue 和 ArrayBlockingQueue。

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列使用PriorityQueue来实现。队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。我们可以将DelayQueue运用在以下应用场景：

缓存系统的设计：可以用DelayQueue保存缓存元素的有效期，使用一个线程循环查询DelayQueue，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。
定时任务调度。使用DelayQueue保存当天将会执行的任务和执行时间，一旦从DelayQueue中获取到任务就开始执行，从比如TimerQueue就是使用DelayQueue实现的。

3.2、BlockingDeque

BlockingDeque（阻塞双端队列）在Deque的基础上实现了双端阻塞等待的功能。和第2节说的类似，BlockingDeque也提供了双端队列该有的阻塞等待方法：

putFirst(E e)：在队首插入元素，如果队列满了，阻塞等待，直到被中断为止。
putLast(E e)：在队尾插入元素，如果队列满了，阻塞等待，直到被中断为止。
offerFirst(E e, long timeout, TimeUnit unit)：向队首插入元素。如果队列满了，阻塞等待timeout个时长，如果到了超时时间还没有空间，抛弃该元素。
offerLast(E e, long timeout, TimeUnit unit)：向队尾插入元素。如果队列满了，阻塞等待timeout个时长，如果到了超时时间还没有空间，抛弃该元素。
takeFirst()：获取并移除队首的元素。如果队列为空，阻塞等待，直到被中断为止。
takeLast()：获取并移除队尾的元素。如果队列为空，阻塞等待，直到被中断为止。
pollFirst(long timeout, TimeUnit unit)：获取并移除队首的元素。如果队列为空，阻塞等待timeout个时长，如果到了超时时间还没有元素，则返回null。
pollLast(long timeout, TimeUnit unit)：获取并移除队尾的元素。如果队列为空，阻塞等待timeout个时长，如果到了超时时间还没有元素，则返回null。
removeFirstOccurrence(Object o)：从队首开始移除第一个和o相等的元素。
removeLastOccurrence(Object o)：从队尾开始移除第一个和o相等的元素。

从图中我们可以知道实现了BlockingDeque的类有：

LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

3.3、TransferQueue

TransferQueue是JDK 1.7对于并发类库新增加的一个接口，它扩展自BlockingQueue，所以自然保持着阻塞队列的所有特性。

有人这样评价它：TransferQueue是是ConcurrentLinkedQueue、SynchronousQueue (公平模式下)、无界的LinkedBlockingQueues等的超集。

TransferQueue对比与BlockingQueue更强大的一点是，生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费（不仅仅是添加到队列里就完事）。新添加的transfer方法用来实现这种约束。顾名思义，阻塞就是发生在元素从一个线程transfer到另一个线程的过程中，它有效地实现了元素在线程之间的传递（以建立Java内存模型中的happens-before关系的方式）。

我们来看看该接口提供的标准方法：

tryTransfer(E e)：若当前存在一个正在等待获取的消费者线程（使用take()或者poll()函数），使用该方法会即刻转移/传输对象元素e并立即返回true；若不存在，则返回false，并且不进入队列。这是一个不阻塞的操作。
transfer(E e)：若当前存在一个正在等待获取的消费者线程，即立刻移交之；否则，会插入当前元素e到队列尾部，并且等待进入阻塞状态，到有消费者线程取走该元素。
tryTransfer(E e, long timeout, TimeUnit unit)：若当前存在一个正在等待获取的消费者线程，会立即传输给它;否则将插入元素e到队列尾部，并且等待被消费者线程获取消费掉；若在指定的时间内元素e无法被消费者线程获取，则返回false，同时该元素被移除。
hasWaitingConsumer()：判断是否存在消费者线程。
getWaitingConsumerCount()：获取所有等待获取元素的消费线程数量。

其实transfer方法在SynchronousQueue的实现中就已存在了,只是没有做为API暴露出来。SynchronousQueue有一个特性:它本身不存在容量,只能进行线程之间的元素传送。SynchronousQueue在执行offer操作时，如果没有其他线程执行poll，则直接返回false.线程之间元素传送正是通过transfer方法完成的。

TransferQueue相比SynchronousQueue用处更广、更好用，因为你可以决定是使用BlockingQueue的方法（例如put方法）还是确保一次传递完成（即transfer方法）。在队列中已有元素的情况下，调用transfer方法，可以确保队列中被传递元素之前的所有元素都能被处理。

从图中我们可以知道实现了TransferQueue的类有：

LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

好了，队列的API先说到这里，下面我会另起一文重点说说阻塞队列的那些个实现类的原理。

转自 http://benjaminwhx.com/2018/05/05/%E8%AF%B4%E8%AF%B4%E9%98%9F%E5%88%97Queue/