Queue整理

队列就是一种特殊的线性表，它只允许在表的头部进行删除操作，在表的尾部进行插入操作。

队列是Java开发中常用的工具，JDK中提供了多种类供我们使用，本文是对这些类的整理。

Queue是JDK中所有队列类的公共接口，它拥有6对方法，分别对应在尾部插入元素、删除头部元素、获取头部元素，但是对于操作失败的处理有所不同：

一类是抛出异常：

• add(e)：插入元素。如果插入成功，返回true，否则抛出IllegalStateException异常。
• remove()：删除元素。如果删除成功，返回头部被删除的元素，否则抛出NoSuchElementException异常。
• element()：获取元素。如果队列不为空，返回头部元素，否则抛出NoSuchElementException异常。

一类是返回特殊的值：

• offer(e)：插入元素。如果插入成功，返回true，否则返回false。
• poll()：删除元素。如果删除成功，返回头部被删除的元素，否则返回null。
• peek()：获取元素。如果队列不为空，返回头部元素，否则返回null。

有多个继承自Queue的接口，分别为BlockingQueue、TransferQueue、Deque、BlockingDeque。

下面分不同接口的实现类来分别进行总结。

Queue

直接实现Queue接口的类不多，如下图所示，只有PriorityQueue和ConcurrentLinkedQueue。

PriorityQueue

PriorityQueue是一个基于堆的有序无界队列，插入到其中的元素经过堆排序形成一个有序的结构，每次删除元素都从堆的顶部删除。

ConcurrentLinkedQueue

ConcurrentLinkedQueue是一个基于链表的无界队列，插入元素时添加到链表的尾部，删除元素时摘除链表的头结点并返回，元素的顺序遵循先进先出原则。ConcurrentLinkedQueue是一个线程安全的类。

BlockingQueue

BlockingQueue又名阻塞队列，它在Queue接口的基础上添加了阻塞操作的方法。即：

• 当队列满时，队列会阻塞插入元素的线程，直到队列不满
• 当队列空时，队列会阻塞删除元素的线程，直到队列不空

它添加的方法分为两类：

一类是一直阻塞的方法：

• put(e)：插入元素。如果队列满了，等待队列空出位置。等待过程中如果中断线程，抛出InterruptedException异常。
• take()：删除元素。如果队列为空，等待队列有元素进入。等待过程中如果中断线程，抛出InterruptedException异常。

一类是带有超时的阻塞方法：

• offer(e, time, unit)：插入元素。如果队列满了，等待队列空出位置，或者等待时间超时。如果成功插入元素则返回true，如果等待时间超时则返回false。等待过程中如果中断线程，抛出InterruptedException异常。
• poll(time, unit)：删除元素。如果队列为空，等待队列有元素进入，或者等待时间超时。如果元素删除成功则返回被删除的元素，如果等待时间超时则返回null。等待过程中如果中断线程，抛出InterruptedException异常。

BlockingQueue的实现类如下图所示：

ArrayBlockingQueue

ArrayBlockingQueue是一个基于数组的有界阻塞队列，它在新建时需要指定队列的容量。

ArrayBlockingQueue使用Condition信号量来达到阻塞的目的。默认对锁的抢占是非公平的，可以在新建时指定公平锁。

LinkedBlockingQueue

LinkedBlockingQueue是一个基于链表的有界阻塞队列，它的默认容量为Integer.MAX_VALUE，在新建时可以指定容量。

LinkedBlockingQueue对插入和删除两个操作分配了两个锁，降低了这两个操作竞争锁而阻塞线程的概率，提高了执行效率。

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素，只有在延迟期满时才能从队列中提取元素。

DelayQueue中包含了一个PriorityQueue用于维护元素的顺序。

PriorityBlockingQueue

PriorityBlockingQueue是一个基于堆的有序无界阻塞队列。

PriorityBlockingQueue只使用了一个notEmpty信号量，因为PriorityBlockingQueue是一个无界队列，因此插入元素不需要等待队列不满。

SynchronousQueue

SynchronousQueue是一种特殊的队列，队列中不存储元素。put方法会一直阻塞直到有另外的线程调用take方法获取元素，take方法也类似，只有另外的线程调用put方法插入元素take方法才会返回。

SynchronousQueue相当于是一个线程同步工具。

TransferQueue

TransferQueue接口是对SynchronousQueue的一种抽象，它定义了生产者和消费者线程相互阻塞的操作。它定义了几个方法：

• tryTransfer(e)：尝试将元素交给消费者线程
• transfer(e)：一直阻塞，等待将元素交给消费者线程
• tryTransfer(e, timeout, unit)：等待将元素交给消费者线程，一定时间后返回
• hasWaitingConsumer()：判断是否有等待的消费者线程
• getWaitingConsumerCount()：获得消费者线程的数量

LinkedTransferQueue

LinkedTransferQueue是TransferQueue的实现类，它综合了LinkedBlockingQueue和SynchronousQueue的功能。LinkedTransferQueue通过CAS保证线程安全性，相比于LinkedBlockingQueue提高了效率。

transfer方法需要等待消费者线程消费元素。put方法判断是否有等待的消费线程，如果有则直接将元素交给消费线程，否则将元素添加到队列中，不会一直等待消费者线程。

Deque

Deque被称为双端队列。和队列相比，双端队列可以在头部和尾部都进行插入和删除操作。它定义了以下方法：

头部操作方法，根据失败操作的处理分为两类：

抛出异常

• addFirst(e)：在头部插入元素，如果队列已满则抛出IllegalStateException异常。
• removeFirst()：在头部删除元素，如果队列为空则抛出NoSuchElementException异常。
• getFirst()：获取头部元素，如果队列为空则抛出NoSuchElementException异常。

返回特殊值

• offerFirst(e)：在头部插入元素，如果插入成功则返回true，队列已满则返回false。
• pollFirst()：在头部删除元素，如果队列为空则返回null，否则返回队列头部的元素。
• peekFirst()：获取头部元素，如果队列为空则返回null，否则返回队列头部的元素。

尾部操作方法，根据失败操作的处理分为两类：

抛出异常

• addLast(e)：在尾部插入元素，如果队列已满则抛出IllegalStateException异常。
• removeLast()：在尾部删除元素，如果队列为空则抛出NoSuchElementException异常。
• getLast()：获取尾部元素，如果队列为空则抛出NoSuchElementException异常。

返回特殊值

• offerLast(e)：在尾部插入元素，如果插入成功则返回true，队列已满则返回false。
• pollLast()：在尾部删除元素，如果队列为空则返回null，否则返回队列头部的元素。
• peekLast()：获取尾部元素，如果队列为空则返回null，否则返回队列头部的元素。

和Queue相比，Deque有几个相等的方法：

Queue中的方法	Deque中相等的方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

和Stack相比，Deque有几个相等的方法：

Stack中的方法	Deque中相等的方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

ArrayDeque

ArrayDeque是一个基于数组的无界双端队列。

LinkedList

LinkedList是一个基于双向链表的无界双端队列。

ConcurrentLinkedDeque

ConcurrentLinkedDeque是一个基于双向链表的无界双端队列。它是一个线程安全类。

BlockingDeque

BlockingDeque是阻塞双端队列，即队列为空时在队列两端的删除操作都会被阻塞，队列已满时在队列两端的插入操作都会被阻塞。

相比于Deque，BlockingDeque定义了一些阻塞方法：

头部操作方法，根据是否有超时时间分为两类：

一直阻塞：

• putFirst(e)：在头部插入元素。如果队列满了，等待队列空出位置。等待过程中如果中断线程，抛出InterruptedException异常。
• takeFirst()：在头部删除元素。如果队列为空，等待队列有元素进入。等待过程中如果中断线程，抛出InterruptedException异常。

超时时间：

• offerFirst(e, time, unit)：在头部插入元素。如果队列满了，等待队列空出位置，或者等待时间超时。如果成功插入元素则返回true，如果等待时间超时则返回false。等待过程中如果中断线程，抛出InterruptedException异常。
• pollFirst(time, unit)：在头部删除元素。如果队列为空，等待队列有元素进入，或者等待时间超时。如果元素删除成功则返回被删除的元素，如果等待时间超时则返回null。等待过程中如果中断线程，抛出InterruptedException异常。

尾部操作方法，根据是否有超时时间分为两类：

一直阻塞：

• putLast(e)：在尾部插入元素。如果队列满了，等待队列空出位置。等待过程中如果中断线程，抛出InterruptedException异常。
• takeLast()：在尾部删除元素。如果队列为空，等待队列有元素进入。等待过程中如果中断线程，抛出InterruptedException异常。

超时时间：

• offerLast(e, time, unit)：在尾部插入元素。如果队列满了，等待队列空出位置，或者等待时间超时。如果成功插入元素则返回true，如果等待时间超时则返回false。等待过程中如果中断线程，抛出InterruptedException异常。
• pollLast(time, unit)：在尾部删除元素。如果队列为空，等待队列有元素进入，或者等待时间超时。如果元素删除成功则返回被删除的元素，如果等待时间超时则返回null。等待过程中如果中断线程，抛出InterruptedException异常。

LinkedBlockingDeque

LinkedBlockingDeque是一个基于链表的有界阻塞双端队列。

https://docs.oracle.com/javase/8/docs/api/index.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/BlockingQueue.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/TransferQueue.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/BlockingDeque.html
https://juejin.im/post/6844903657436086285
https://juejin.im/post/6844903662460878861
https://juejin.im/post/6844903600431480840