如果要实现一个线程安全的队列有两种方式：一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现。非阻塞的实现方式则可以使用CAS循环的方式来实现。ConcurrentLinkedQueue就是非阻塞的。

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序。它采用了“wait-free”算法(即CAS算法)来实现。

1.结构

ConcurrentLinkedQueue由head节点和tail节点组成，每个节点由节点元素和指向下一个节点的引用组成。
默认情况下head节点存储的元素为空，tail节点等于head节点。

2.入队

入队主要做两件事情
1.将入队节点设置成当前队列尾节点的下一个节点。
2.更新tail节点。
如果tail节点的next节点不为空，则将入队节点设置成tail节点；
如果tail节点的next节点为空，则将入队节点设置成tail的next节点，所以tail节点不总是尾节点。

3.出队

出队列就是从队列里返回一个元素，并清空该节点对元素的引用。

首先获取头节点的元素，然后判断头节点元素是否为空。
如果为空，表示另外一个线程已经进行了一次出队操作将该节点的元素取走，那么获取下一个节点。
如果不为空，则使用CAS的方式将头结点的引用设置成null，如果CAS成功，则直接返回头结点的元素，如果不成功，表示另外一个线程已经进行了一次出队操作更新了head节点，导致元素发生了变化，需要重新获取头节点。