Java中的Queue之概述

对技术还是得有敬畏之心，总觉得Queue好像没啥，其实只是没有仔细去了解过。不过自从上次认真地看了线程池的源代码之后，发现Queue是一个很神奇的集合类。Queue的形式有无界、有界，还有堵塞、非堵塞。初略想想，这个实现可能就不简单。一个问题在线程池中，自定义线程池时，放入什么样的队列可以让线程数达

对技术还是得有敬畏之心，总觉得Queue好像没啥，其实只是没有仔细去了解过。

不过自从上次认真地看了线程池的源代码之后，发现Queue是一个很神奇的集合类。Queue的形式有无界、有界，还有堵塞、非堵塞。初略想想，这个实现可能就不简单。

一个问题

在线程池中，自定义线程池时，放入什么样的队列可以让线程数达不到maximumPoolSize？

按照线程池的源码，线程增长有两个阶段：一个阶段是在达到corePoolSize之前，第二个阶段是在达到corePoolSize之后并且阻塞队列已经满了，才会继续增加线程，直到maximumPoolSize。

所以解决方案有如下两种：

①如果队列是无界的，那么将不会到达第二阶段的增长，也就无法到达maximumPoolSize；

②还有可以让corePoolSize在足够大的值，同时限定堆大小，保证在有限的任务数下，引发内存不足也算是一种解决方案。

在解决方案①的基础上，我给出了LinkedBlockingQueue这个答案，但是它是一个“有界”的堵塞队列，只是它的capacity默认是Integer.MAX_VALUE。因为一开始我得知它是一个无界队列，因为未做详细、深入的了解，但是后面我被指正后，引发了我对Queue的思考，因为不常用，所以了解的确不是很多；同时，Queue不仅仅是一个FIFO，还有同步操作在里面，就是生产者-消费者的同步问题的一个解决方案。综上，这让我对堵塞队列产生了强烈的兴趣。

概览

找了一下BlockingQueue大致的实现类，它们的类图如下。

从中可以看出，它们都继承自AbstractQueue，并且都实现了BlockingQueue接口，只有LinkedTransferQueue还实现了TransferQueue。加上对Queue的一些操作并不是特别熟悉，比如offer、peek、poll之类，所以从Queue接口开始，逐个了解其大致的功能。

Queue

这个接口定义了6个方法，功能分成3个，分别是插入、删除、获取队首元素，每个功能有2种实现，对应如下表中的关系。这两种实现的区别也很明显

	Throws exception	Returns special value
Insert	`add(e)`	`offer(e)`
Remove	`remove()`	`poll()`
Examine	`element()`	`peek()`

add(e) 和 offer(e)：添加失败时，add抛异常，offer返回false。
remove() 和 poll() ：没有元素时，remove抛异常，poll返回null。
element() 和 peek()：没有元素时，remove抛异常，peek返回null。

还有一点需要注意，虽然有的Queue的实现（LinkedList）允许插入null值，但是Queue通常不允许插入null值，因为null对peek、poll来说，是queue中没有元素。

BlockingQueue

继承自Queue接口，同时在Queue的基础上，新增了堵塞插入、堵塞获取并删除、可堵塞一定时长的插入、可堵塞一定时长的获取并删除。相应关系对应下表。

	Throws exception	Special value	Blocks	Times out
Insert	`add(e)`	`offer(e)`	`put(e)`	`offer(e, time, unit)`
Remove	`remove()`	`poll()`	`take()`	`poll(time, unit)`
Examine	`element()`	`peek()`	not applicable	not applicable

put(e) 和 offer(e, time, unit)：put一直堵塞直到空间可用，offer(e, time, unit)只堵塞特定时长。
take() 和 poll(time, unit)： take一直堵塞直到元素可用，poll(time, unit)只堵塞特定时长。

BlockingQueue设计主要被用来处理生产者-消费者问题。还有一点需要注意，BlockingQueue不接受null元素。插入操作happen-before读取、移除。

AbstractQueue

抽象类，继承自AbstractCollection，并实现了Queue接口，但未给出具体实现，相当于引入Queue相应方法，在自身类中使用，然后靠子类实现Queue的相关方法。

它实现的add、remove、element方法，分别依靠offer、poll、peek，具体如下：

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();
}

public void clear() {
    while (poll() != null)
        ;
}

正好对应于上面Queue方法的区别。

常见实现类

Java中线程安全的内置队列如下表所示。队列的底层一般分成三种：数组、链表和堆。其中，堆一般情况下是为了实现带有优先级特性的队列。

队列	有界性	锁	数据结构
ArrayBlockingQueue	bounded	加锁	arraylist
LinkedBlockingQueue	optionally-bounded	加锁	linkedlist
ConcurrentLinkedQueue	unbounded	无锁	linkedlist
LinkedTransferQueue	unbounded	无锁	linkedlist
PriorityBlockingQueue	unbounded	加锁	heap
DelayQueue	unbounded	加锁	heap

基于数组线程安全的队列，比较典型的是ArrayBlockingQueue，它主要通过加锁的方式来保证线程安全；

基于链表的线程安全队列，分成LinkedBlockingQueue和ConcurrentLinkedQueue两大类，前者也通过锁的方式来实现线程安全，而后者以及上面表格中的LinkedTransferQueue都是通过原子变量CAS这种不加锁的方式来实现的。

通过不加锁的方式实现的队列都是无界的（无法保证队列的长度在确定的范围内）；而加锁的方式，可以实现有界队列。

在稳定性要求特别高的系统中，为了防止生产者速度过快，导致内存溢出，只能选择有界队列；同时，为了减少Java的垃圾回收对系统性能的影响，会尽量选择array/heap格式的数据结构。

Reference：

https://tech.meituan.com/2016/11/18/disruptor.html

https://www.cnblogs.com/WangHaiMing/p/8798709.html

https://www.cnblogs.com/stateis0/p/9062076.html