摘要：前面详细分析了AQS内部的阻塞队列实现原理：基于双向链表，通过对head/tail进行CAS操作，实现入队和出队。

前面详细分析了AQS内部的阻塞队列实现原理：基于双向链表，通过对head/tail进行CAS操作，实现入队和出队。

ConcurrentLinkedQueue 的实现原理和AQS 内部的阻塞队列类似：同样是基于 CAS，同样是通过head/tail指针记录队列头部和尾部，但还是有稍许差别。

首先，它是一个单向链表，定义如下。

其次，在AQS的阻塞队列中，每次入队后，tail一定后移一个位置；每次出队，head一定前移一个位置，以保证head指向队列头部，tail指向链表尾部。

但在ConcurrentLinkedQueue中，head/tail的更新可能落后于节点的入队和出队，因为它不是直接对 head/tail指针进行 CAS操作的，而是对 Node中的 item进行操作。下面进行详细分析：

1.初始化

初始的时候，如图5-5所示，head和tail都执行一个NULL节点。对应的代码如下。

2.入队列

代码如下所示。

上面的入队其实是每次在队尾追加2个节点时，才移动一次tail节点，具体过程如图5-6所示。

初始的时候，队列中有1个节点item1，tail指向该节点，假设线程1要入队item2节点：

step1:p=tail,q=p.next=NULL.

step2：对p的next执行CAS操作，追加item2，成功之后，p=tail。所以上面的casTail函数不会执行，直接返回。此时tail指针没有变化。

图5-6 线程1入队item2节点

之后，假设线程2要入队item3节点，如图5-7所示。

step3:p=tail,q=p.next.

step4：q！=NULL，因此不会入队新节点。p，q都后移1位。

step5：q=NULL，对p的next执行CAS操作，入队item3节点。

step6：p！=t，满足条件，执行上面的casTail操作，tail后移2个位置，到达队列尾部。

图5-7 线程2入队item3节点

最后总结一下入队列的两个关键点：

（1）即使tail指针没有移动，只要对p的next指针成功进行CAS操作，就算成功入队列。

（2）只有当 p！=tail的时候，才会后移tail指针。也就是说，每连续追加2个节点，才后移1次tail指针。即使CAS失败也没关系，可以由下1个线程来移动tail指针。

3.出队列

上面说了入队列之后，tail指针不变化，那是否会出现入队列之后，要出队列却没有元素可出的情况呢？

出队列的代码和入队列类似，也有p、q2个指针，整个变化过程如图5-8所示。假设初始的时候head指向空节点，队列中有item1、item2、item3 三个节点。

step1:p=head,q=p.next.p!=q.

step2：后移p指针，使得p=q。

step3：出队列。关键点：此处并没有直接删除item1节点，只是把该节点的item通过CAS操作置为了NULL。

step4：p！=head，此时队列中有了2个 NULL 节点，再前移1次head指针，对其执行updateHead操作。

图5-8 线程3出队列的过程

最后总结一下出队列的关键点：

（1）出队列的判断并非观察 tail 指针的位置，而是依赖于 head 指针后续的节点是否为NULL这一条件。

（2）只要对节点的item 执行CAS操作，置为NULL成功，则出队列成功。即使head指针没有成功移动，也可以由下1个线程继续完成。

4.队列判空

因为head/tail 并不是精确地指向队列头部和尾部，所以不能简单地通过比较 head/tail 指针来判断队列是否为空，而是需要从head指针开始遍历，找第1个不为NULL的节点。如果找到，则队列不为空；如果找不到，则队列为空。代码如下所示。

来源：程序员高级码农II一点号