文章主要介绍Java线程安全的非阻塞队列ConcurrentLinkedQueue的原理和常用API

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列是一种容器。

队列模型

ConcurrentLinkedQueue队列

ConcurrentLinkedQueue：是一种线程安全的非阻塞队列，一个基于链表的无界线程安全队列。此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部是队列中时间最长的元素。队列的尾部是队列中时间最短的元素。新的元素插入到队列的尾部，队列获取操作从队列头部获得元素

阻塞和非阻塞

阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态.

阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。

非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程

ConcurrentLinkedQueue 的非阻塞实现原理是：使用循环CAS(CAS是一种原子操作方式，Java中的Unsafe类是他的一个抽象，该类中的每个方法都相当与一条机器指令，CAS+volatile构成Java并发包)的方式来添加，获取，修改数据，保证数据的可见性，也就保证了线程安全。由于不断循环CAS操作，即使不同的线程操作同一个CAS方法，只要有一个线程操作成功，就会立即刷新内存，其他线程就会立即得到最新的数据，而不会导致在多线程环境下数据不一致的问题。线程也不会出现阻塞的情况。

ConcurrentLinkedQueue原理

首先ConcurrentLinkedQueue中的链表结构（该篇文章中使用JDK1.8环境）

Java利用内存存储数据的方式有两种，一种是数组，在内存中划出一段连续的空间存储数据，使用下标维护数据之间的联系，一种是链表可以利用分散内存空间，使用索引来维护数据之前的联系

使用Node<E>作为节点         item：表示该节点的内容，next:表示下一个节点的索引

在ConcurrentLinkedQueue中定义了一个head节点用来出队列使用，一个tail节点用来入队列使用，初始化的时候head = tail 都是一个空节点

下面通过ConcurrentLinkedQueue的入队列来解释为什么是线程安全的。

ConcurrentLinkedQueue的入队列

模拟四个元素添加到ConcurrentLinkedQueue中

添加元素1。队列更新head节点的next节点为元素1节点。又因为tail节点默认情况下等于head节点，所以它们的next节点都指向元素1节点。

添加元素2。队列首先设置元素1节点的next节点为元素2节点，然后更新tail节点指向元素2节点。

添加元素3，设置tail节点的next节点为元素3节点。

添加元素4，设置元素3的next节点为元素4节点，然后将tail节点指向元素4节点。

通过调试入队过程并观察head节点和tail节点的变化，发现入队主要做两件事情：第一是将入队节点设置成当前队列尾节点的下一个节点；第二是更新tail节点，如果tail节点的next节点不为空，则将入队节点设置成tail节点，如果tail节点的next节点为空，则将入队节点设置成tail的next节点，所以tail节点不总是尾节点。

下面查看入队的源代码来解释上面这句话

offer()源码

从源代码角度来看，整个入队过程主要做两件事情：第一是定位出尾节点；第二是使用CAS算法将入队节点设置成尾节点的next节点，如不成功则重试。

为什么offer()方法是线程安全的

原因在于CAS算法，在p.casNext(null, newNode)这个方法中

nextOffset：是一个内存的物理位置，表示该节点的next节点的内存地址

如果nextOffset的内存位置的数据和cmp相同，就将nextOffset的内存位置的数据换成val,这个是一个原子操作，线程安全。

当一个线程A进入这个方法的时候，说明找到了尾节点p(尾节点的next为null)。即使这个时候A线程挂起，B线程进行添加，或者修改了尾节点,导致A线程的尾节点发生改变，这个时候A线程恢复继续执行p.casNext(null, newNode)方法由于第一个参数为null 但是尾节点发生改变使得线程A的p节点(不能说是尾节点，因为尾节点在B线程已经修改)的nextOffset指向的物理地址不是null的物理地址，所以不能替换，该方法返回false,线程A继续循环寻找尾节点。

常用API

add(E e)：插入一个元素到队尾，返回boolean的插入结果

contains(Object o)：是否包含某个元素，包含返回true

isEmpty()：判断是否为空，为空返回true

iterator()：遍历队列元素，返回Iterator<E e>

offer(E e)：插入一个元素到队尾，返回boolean的插入结果

peek()：检索但不移除此队列的头部，如果此队列为空，则返回null

poll()：检索并删除此队列的头部，如果此队列为空，则返回null

remove(Object o)：从此队列中删除指定元素的单个实例（如果存在）

size()：返回此队列中的元素数

toArray()：以适当的顺序返回包含此队列中所有元素的数组。