队列：遵循FIFO（先入先出）的原则，在Java中与List,Set处于同一级别。

Java中的队列

在java中Queue又分为双端队列，阻塞队列，非阻塞队列三种。

我们先看一下接口Queue定义的方法：

boolean add(e);boolean offer(E e);E remove();E poll();E element();E peek();

每个Queue方法都有两种形式：

（1）如果操作失败则抛出异常，

（2）如果操作失败，则返回特殊值（null或false，具体取决于操作），接口的常规结构如下表所示

Queue从Collection继承的add方法插入一个元素，除非它违反了队列的容量限制，在这种情况下它会抛出IllegalStateException；offer方法与add不同之处仅在于它通过返回false来表示插入元素失败。

remove和poll方法都移除并返回队列的头部，确切地移除哪个元素是由具体的实现来决定的，仅当队列为空时，remove和poll方法的行为才有所不同，在这些情况下，remove抛出NoSuchElementException，而poll返回null。

element和peek方法返回队列头部的元素，但不移除，它们之间的差异与remove和poll的方式完全相同，如果队列为空，则element抛出NoSuchElementException，而peek返回null。

队列一般不要插入空元素。

BlockingQueue

BlockingQueue位于JUC中，熟称阻塞队列， 阻塞队列首先它是一个队列，继承Queue接口，是队列就会遵循先进先出（FIFO）的原则，又因为它是阻塞的，故与普通的队列有两点区别：

当一个线程向队列里面添加数据时，如果队列是满的，那么将阻塞该线程，暂停添加数据

当一个线程从队列里面取出数据时，如果队列是空的，那么将阻塞该线程，暂停取出数据

BlockingQueue相关方法：

重点，再来解释一下，加深印象：

3个可能会有异常的方法，add、remove、element；这3个方法不会阻塞（是说队列满或者空的情况下是否会阻塞）；队列满的情况下，add抛出异常；队列为空情况下，remove、element抛出异常offer、poll、peek 也不会阻塞（是说队列满或者空的情况下是否会阻塞）；队列满的情况下，offer返回false；队列为空的情况下，pool、peek返回null队列满的情况下，调用put方法会导致当前线程阻塞队列为空的情况下，调用take方法会导致当前线程阻塞offer(e,timeuout,unit)，超时之前，插入成功返回true，否者返回falsepoll(timeout,unit)，超时之前，获取到头部元素并将其移除，返回true，否者返回false

以上一些方法希望大家都记住，方便以后使用

BlockingQueue常见的实现类

ArrayBlockingQueue

基于数组的阻塞队列实现，其内部维护一个定长的数组，用于存储队列元素。线程阻塞的实现是通过ReentrantLock来完成的，数据的插入与取出共用同一个锁，因此ArrayBlockingQueue并不能实现生产、消费同时进行。而且在创建ArrayBlockingQueue时，我们还可以控制对象的内部锁是否采用公平锁，默认采用非公平锁。

LinkedBlockingQueue

基于单向链表的阻塞队列实现，在初始化LinkedBlockingQueue的时候可以指定大小，也可以不指定，默认类似一个无限大小的容量（Integer.MAX_VALUE），不指队列容量大小也是会有风险的，一旦数据生产速度大于消费速度，系统内存将有可能被消耗殆尽，因此要谨慎操作。另外LinkedBlockingQueue中用于阻塞生产者、消费者的锁是两个（锁分离），因此生产与消费是可以同时进行的。

PriorityBlockingQueue

一个支持优先级排序的无界阻塞队列，进入队列的元素会按照优先级进行排序

SynchronousQueue

同步阻塞队列，SynchronousQueue没有容量，与其他BlockingQueue不同，SynchronousQueue是一个不存储元素的BlockingQueue，每一个put操作必须要等待一个take操作，否则不能继续添加元素，反之亦然

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列，里面的元素全部都是“可延期”的元素，列头的元素是最先“到期”的元素，如果队列里面没有元素到期，是不能从列头获取元素的，哪怕有元素也不行，也就是说只有在延迟期到时才能够从队列中取元素

LinkedTransferQueue

LinkedTransferQueue是基于链表的FIFO无界阻塞队列，它出现在JDK7中，Doug Lea 大神说LinkedTransferQueue是一个聪明的队列，它是ConcurrentLinkedQueue、SynchronousQueue(公平模式下)、无界的LinkedBlockingQueues等的超集，LinkedTransferQueue包含了ConcurrentLinkedQueue、SynchronousQueue、LinkedBlockingQueue三种队列的功能

相对于其他阻塞队列，LinkedTransferQueue多了tryTransfer和transfer方法。LinkedTransferQueue类继承自AbstractQueue抽象类，并且实现了TransferQueue接口：

public interface TransferQueue<E> extends BlockingQueue<E> {// 如果存在一个消费者已经等待接收它，则立即传送指定的元素，否则返回false，并且不进入队列。boolean tryTransfer(E e);// 如果存在一个消费者已经等待接收它，则立即传送指定的元素，否则等待直到元素被消费者接收。void transfer(E e) throws InterruptedException;// 在上述方法的基础上设置超时时间boolean tryTransfer(E e, long timeout, TimeUnit unit)throws InterruptedException;// 如果至少有一位消费者在等待，则返回trueboolean hasWaitingConsumer();// 获取所有等待获取元素的消费线程数量int getWaitingConsumerCount();}

非阻塞队列

基于链接节点的、无界的、线程安全。此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部，队列检索操作从队列头部获得元素。当许多线程共享访问一个公共 collection ,ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许 null 元素。

ConcurrentLinkedQueue 类图结构：

如图ConcurrentLinkedQueue中有两个volatile类型的Node节点分别用来存放列表的首尾节点，其中head节点存放链表第一个item为null的节点，tail则并不是总指向最后一个节点。Node节点内部则维护一个变量item用来存放节点的值，next用来存放下一个节点，从而链接为一个单向无界列表。

public ConcurrentLinkedQueue() {head = tail = new Node<E>(null);}

如上代码初始化时候会构建一个item为NULL的空节点作为链表的首尾节点。

offer操作

offer操作是在链表末尾添加一个元素，下面看看实现原理。

从构造函数知道一开始有个item为null的哨兵节点，并且head和tail都是指向这个节点，下面看下当一个线程调用offer时候的情况：

如图首先查找尾节点，q==null,p就是尾节点，所以执行p.casNext通过cas设置p的next为新增节点，这时候p==t所以不重新设置尾节点为当前新节点。由于多线程可以调用offer方法，所以可能两个线程同时执行到了（1）进行cas，那么只有一个会成功（假如线程1成功了），成功后的链表为：

失败的线程会循环一次这时候指针为：

这时候会执行（3）所以p=q,然后在循环后指针位置为：

所以没有其他线程干扰的情况下会执行（1）执行cas把新增节点插入到尾部，没有干扰的情况下线程2 cas会成功，然后去更新尾节点tail,由于p!=t所以更新。这时候链表和指针为：

假如线程2cas时候线程3也在执行，那么线程3会失败，循环一次后，线程3的节点状态为：

这时候p!=t ；并且t的原始值为told，t的新值为tnew ,所以told!=tnew，所以 p=tnew=tail;

然后在循环一下后节点状态:

q==null所以执行（1）。

现在就差p==q这个分支还没有走，这个要在执行poll操作后才会出现这个情况。poll后会存在下面的状态

这个时候添加元素时候指针分布为：

所以会执行（2）分支 结果 p=head，然后循环，循环后指针分布：

所以执行(1),然后p!=t所以设置tail节点。现在分布图：

自引用的节点会被垃圾回收掉。

add操作

add操作是在链表末尾添加一个元素，下面看看实现原理。其实内部调用的还是offer

public boolean add(E e) {return offer(e);}

poll操作

poll操作是在链表头部获取并且移除一个元素，下面看看实现原理。

当队列为空时候：

可知执行（3）这时候有两种情况，第一没有其他线程添加元素时候(3)结果为true然后因为h!=p为false所以直接返回null。第二在执行q=p.next前，其他线程已经添加了一个元素到队列，这时候（3）返回false，然后执行（5）p=q,然后循环后节点分布：

这时候执行（1）分支，进行cas把当前节点值值为null，同时只有一个线程会成功，cas成功 标示该节点从队列中移除了，然后p!=h,调用updateHead方法，参数为h,p;h!=p所以把p变为当前链表head节点，然后h节点的next指向自己。现在状态为：

cas失败 后 会再次循环，这时候分布图为：

这时候执行（3）返回null.

现在还有个分支（4）没有执行过，那么什么时候会执行那？

这时候执行（1）分支，进行cas把当前节点值值为null，同时只有一个线程A会成功，cas成功 标示该节点从队列中移除了，然后p!=h,调用updateHead方法，假如执行updateHead前另外一个线程B开始poll这时候它p指向为原来的head节点，然后当前线程A执行updateHead这时候B线程链表状态为：

所以会执行（4）重新跳到外层循环，获取当前head,现在状态为：

peek操作

peek操作是获取链表头部一个元素（只读取不移除），下面看看实现原理。

代码与poll类似，只是少了castItem.并且peek操作会改变head指向，offer后head指向哨兵节点，第一次peek后head会指向第一个真的节点元素。

size操作

获取当前队列元素个数，在并发环境下不是很有用，因为使用CAS没有加锁所以从调用size函数到返回结果期间有可能增删元素，导致统计的元素个数不精确。

remove操作

如果队列里面存在该元素则删除给元素，如果存在多个则删除第一个，并返回true，否者返回false

contains操作

判断队列里面是否含有指定对象，由于是遍历整个队列，所以类似size 不是那么精确，有可能调用该方法时候元素还在队列里面，但是遍历过程中才把该元素删除了，那么就会返回false.

案例：

Tomcat中NioEndPoint中的每个poller里面就维护一个ConcurrentLinkedQueue用来作为缓冲存放任务。

ConcurrentLinkedQueue使用CAS非阻塞算法实现使用CAS解决了当前节点与next节点之间的安全链接和对当前节点值的赋值。由于使用CAS没有使用锁，所以获取size的时候有可能进行offer，poll或者remove操作，导致获取的元素个数不精确，所以在并发情况下size函数不是很有用。另外第一次peek或者first时候会把head指向第一个真正的队列元素。

下面总结下如何实现线程安全的，可知入队出队函数都是操作volatile变量：head，tail。所以要保证队列线程安全只需要保证对这两个Node操作的可见性和原子性，由于volatile本身保证可见性，所以只需要看下多线程下如果保证对着两个变量操作的原子性。

对于offer操作是在tail后面添加元素，也就是调用tail.casNext方法，而这个方法是使用的CAS操作，只有一个线程会成功，然后失败的线程会循环一下，重新获取tail，然后执行casNext方法。对于poll也是这样的。

LinkedBlockingQueue和ConcurrentLinkedQueue适用场景

适用阻塞队列的好处：多线程操作共同的队列时不需要额外的同步，另外就是队列会自动平衡负载，即那边（生产与消费两边）处理快了就会被阻塞掉，从而减少两边的处理速度差距。

当许多线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。

LinkedBlockingQueue 多用于任务队列

ConcurrentLinkedQueue 多用于消息队列

多个生产者，对于LBQ性能还算可以接受；但是多个消费者就不行了mainLoop需要一个timeout的机制，否则空转，cpu会飙升的。LBQ正好提供了timeout的接口，更方便使用

如果CLQ，那么我需要收到处理sleep

单生产者，单消费者 用 LinkedBlockingqueue

多生产者，单消费者 用 LinkedBlockingqueue

单生产者 ，多消费者 用 ConcurrentLinkedQueue

多生产者 ，多消费者 用 ConcurrentLinkedQueue