持续更新中：
对队列的操作是不上锁的，属于无锁编程，关于无锁编程的范式可以参考：？待添加？
理解ConcurrentLinkedQueue的实现是理解该类实现的前提，ConcurrentLinkedQueue的分析参考：JUC-ConcurrentLinkedQueue的设计分析与实现
目录
设计与实现
基本结构
不变式
入栈操作
出栈操作
实现的一些细节：
官方文档翻译
设计与实现
基本结构
该队列是由一个个Node节点连接而成的双向队列，Node定义如下
class Node{ volatile Node prev, next; volatile E item; }
不变式
首先提出整个队列设计和实现过程中基本的不变式（利用和维护不变式是许多复杂编程清晰化的重要手段），在实现过程中会看到不变式是如何帮助到我们的：
1，任何时候，队列中只有队头的prev指针为null，只有队尾的next指针为null，分别称队头，队尾为first，last。从队头或队尾出发，如果没有发生竞争那么可以遍历到队列中保存的所有item，如果发生竞争，那么重新读取队头队尾值，此时再次从队头和队尾出发即可。
注意：实际上还有两个哨兵节点也满足prev，next为null这个性质，但是他们另一个指针指向自身因此很容易区分。稍后会介绍这两个哨兵节点并说明这两个哨兵节点的作用。
2，队列设置了两个指针head和tail，如果没有发生前向竞争，从head出发向前遍历一定可以到达队头，如果发生前向竞争那么重新读取head的值（此时head值会改变），再次尝试直到没有前向竞争即可。tail同理，tail关注后向竞争。
注意：head和tail的作用就是用来定位队头和队尾，但head和tail不一定正好在队头和队尾上，这种松弛的设定可以减少volatile写的次数（代价就是会增加volatile读的次数，volatile读的代价比写小很多）。
3，向后遍历的过程中，如果发现一个节点的next指向自身，或者遇到了后向哨兵，那么说明发生了后向竞争。向前遍历的过程中如果发现节点的prev指向了自身，或者遇到了前向哨兵，那么说明发生了前向竞争。如果遍历过程中没有发生前述任何一种情况，那么可以认为此次遍历是无竞争的，没有竞争的操作是可以并发的。
关于两个哨兵节点：
前遍历结束哨兵节点，PREV_TERMINATOR，其prev为null，next指向自身；后遍历结束哨兵节点，NEXT_TERMINATOR，其next为null，prev指向自身。这两个哨兵节点的作用是用来近似的表示队列头和队列尾，当遍历过程中发现一个节点的某个指针指向哨兵节点时说明发生了冲突，虽然此时发生了冲突，队列结构发生了变化，但有些情况下可以认为已经到达了队头或队尾。不过对于入栈和出栈等必须找到真正的队头和队尾的操作来说，哨兵节点这种近似是不可取的。
因为队头和队尾的处理是对称的，因此下面的讨论只以队头进行举例说明。
从以上3条不变式可以知道，寻找队头只需从head向前遍历，直到遇到prev为null的节点即可。如果遍历过程中发现prev指向自身或者到达哨兵节点，那么根据不变式3和2重新读取head值再次尝试向前遍历。
到此，我们可以尝试编写元素入栈的代码
入栈操作
public boolean offerFirst(E e) {
Node newNode = new Node<>(e);
restartFromHead:
for (;;) {
// 不断向前遍历找队头
for (Node h = head, p = h, q;;) {
// 根据不变式1，当前继为null则是到了队头或者前哨兵
if ((q = p.prev) == null) {
// 到了前哨兵，根据不变式3，2表明发生竞争，那么重新从head出发
if (p.next == p) continue restartFromHead;
// 到达队头尝试将新节点插入到队头（p是队头）
newNode.lazySetNext(p);
if (p.casPrev(null, newNode)) {
if (h != p) {
// 尝试跳跃式更新head为新节点，失败也没关系，不变式不会被破坏
casHead(h, newNode);
}
return true;
}
}
// 根据不变式3，2，遇到prev指向自身的节点，重新从head出发
else if (q == p) {
continue restartFromHead;
}
else {
// 没有检测到前向冲突，继续向前
p = q;
}
}
}
}
// 整个入栈过程并没有破坏不变式
根据以上三个不变式，我们写出了入栈的代码，并且入栈过程3条不变式的性质得到保证（因为不变式得到了维持，这样下次我们还能根据不变式来这么入栈）。
所以说编写代码的过程就是利用和维护不变式的过程。
官方的实现有所不同，但本质是一样的，官方代码是利用head是否发生变化来判断是否发生竞争。
出栈操作
出栈操作首先将节点的item置null，表明元素从队列中移除了，然后再将节点从队列中删除（不删除节点也行，毕竟item已经不在队列中了，但是这样会导致队列中存在很多没有意义的item为null的节点影响性能，所以还是要删除这种节点），出栈操作的难点是节点的删除，因此我们先讨论如何删除节点。
unlink的讨论如下：
删除队列中的一个节点p实际上就是将他的前继的next和后继相连，后继的prev和前继相连，这一步操作称之为unlink。但是在多线程的情况下，可能出现以下几种并发导致的竞争情况：
1，其他线程替换了节点p的前继。
2，其他线程替换了节点p的后继。
3，当前有个线程遍历过程中正好遍历到p，此时如果删除了p那么将会导致该线程无法继续遍历过程。
删除的过程必须要处理上述三种竞争，否则将会导致出现混乱的情况。
对于1，2两种情况，节点p将前继和后继相连后检查自身的前继和后继是否发生了变化，如果发生了变化再次连接此时的前继和后继直到没有竞争的情况发生。对于3，其实也非常好处理，那就是保留节点p的next和prev指针原来的值，不去修改，那么当前在p节点上的线程将可以继续从p的next或者prev指针往下遍历。上述三条不变式的性质也还可以得到保持。
但是，对于第3点的处理会存在一个和垃圾回收有关的问题，p的next和prev仍然指向队列中的节点，对于多数垃圾收集器来说，将会影响到后续对队列节点的回收，因此，需要在适当的时候将p的next或者prev赋值为null或者让他们指向p，这样就解除了p对队列中其他节点的引用，这一步操作称为gc-unlinking。
复习一下，目前为止提到了两种unlink操作：
unlink：将节点的后继和前继相连，从而在队列中删除该节点
gc-unlinking：使节点的prev和next指针不在指向队列中的节点，从而解除节点对队列节点的引用
gc-unlinking的讨论如下：
不能将p的next或者prev赋值为null，因为这样会破坏不变式1，例如对于此时停留在节点p的线程t，t会发现p的前继或后继为null，根据不变式1，导致t误认为已经到达了队头和队尾。
因此将p的next或者prev指向自身，但是会有一个问题，t线程后续的遍历将会不断在p处循环，不过，此时基于不变式2我们可以从head出发找到队头，重新开始遍历。但实际上此时不变式2也可能已经被破坏，例如，假设head此时正好位于p上，那么从head出发一样会在p处循环，无法到达队头。因此在删除节点p时，要将head移动到一个安全的位置，那什么样的位置是安全的？将head放到一个不能到达p的位置上就行，这样p把自己gc-unlink就不会影响到head，队列中有两个位置是不可达p的，item不为null的节点以及队头，要理解为什么这两个位置不可达p其实有难度，等看完具体的代码后再尝试想象是不是这样的节点是不可达p的。
但是这又出现一个问题，假设p就是队头，那么显然此时从队头出发又会造成不断在p循环的问题，不变式1被破坏了，因此如果p是队头，就放弃gc-unlink操作。这样问题就完美的解决了。
另外，如果p是队头，也不能把他的后继指向p的prev也就是null，因为这样会导致队列中可能出现两个prev为null的节点（p和p的后继这两个节点）从而破坏不变式1，换句话说如果p是队头，不止不进行gc-unlinking，甚至都不进行unlink操作。
所以说为了垃圾回收，整个实现变得复杂了很多。如果不考虑垃圾回收问题，那么实现就变得轻松很多了。
还有一个问题，上面提到在适当的时候进行gc-unlinking，那什么情况是适当的时候，其实任何时刻都可以进行gc-unlinking，只要gc-unlinking的过程能够保证不变式的性质，但这样会导致频繁的发生冲突，因此只有当节点p是队列端点的节点时，才进行gc-unlinking的操作。
官方代码虽然按照这个思路进行处理，但实现起来没那么简单，一起看下官方代码是如何进行unlink和gc-unlinking处理的：
// unlink成功了才进行gc-unlinking操作，因此gc-unlinking的代码直接放在unlink()函数内 void unlink(Nodex) { // assert x != null; // assert x.item == null; // assert x != PREV_TERMINATOR; // assert x != NEXT_TERMINATOR; final Node prev = x.prev; final Node next = x.next; // 如上面的讨论，对于队头/队尾进行特殊处理，稍后看具体的代码 if (prev == null) { unlinkFirst(x, next); } else if (next == null) { unlinkLast(x, prev); } else { // Unlink interior node. // // This is the common case, since a series of polls at the // same end will be "interior" removes, except perhaps for // the first one, since end nodes cannot be unlinked. // // At any time, all active nodes are mutually reachable by // following a sequence of either next or prev pointers. // // Our strategy is to find the unique active predecessor // and successor of x. Try to fix up their links so that // they point to each other, leaving x unreachable from // active nodes. If successful, and if x has no live // predecessor/successor, we additionally try to gc-unlink, // leaving active nodes unreachable from x, by rechecking // that the status of predecessor and successor are // unchanged and ensuring that x is not reachable from // tail/head, before setting x's prev/next links to their // logical approximate replacements, self/TERMINATOR. Node activePred, activeSucc; boolean isFirst, isLast; int hops = 1; // Find active predecessor // 首先找到节点x的item不为null的前继，因为item为null的前继没必要留在队列中 // 在找x的前继时同时检查x是否队列端点处的节点，因为在上面讨论中提到过，当x是 // 从端点出队时，才对x进行gc-unlink，其中isFirst就是记录x是否是在端点的变量 for (Node p = prev; ; ++hops) { if (p.item != null) { // 找到有效的item不为null的前继，可以退出该循环， // 此时显然x不在端点，因为在他的前面有item不为null的 // 节点，因此isFirst为假 activePred = p; isFirst = false; break; } Node q = p.prev; if (q == null) { // 遇到了前继哨兵，表明发生了冲突，此时放弃修改，直接返回，因 // 为在这种情况下找x的前继续不是很方便。虽然这样可能导致该节 // 点存留在队列中（注意只是节点在队列中，节点中的item已经不在队列中了， // 因为x.item在进入该函数之前已经置null了），但是后续的队列unlink操 // 作迟早会将x的节点回收 if (p.next == p) return; // 表明遇到了队头，队头一定是一个有效的前继或者说有效的节点，这是 // 设计上规定好的，不变式会维护这个设计，不过因为这种情况下x有有效 // 前继（也就是队头）的item为null，因此 // isFirst为真，表明x是队列端点处的节点 activePred = p; isFirst = true; break; } // 同遇到前继哨兵一样，表明发生了冲突，一样的处理方式， // 直接返回，交给后续的队列unlink操作处理 else if (p == q) return; else // 还没有找到，继续向前 p = q; } // Find active successor // 找后继，处理同上 for (Node p = next; ; ++hops) { if (p.item != null) { activeSucc = p; isLast = false; break; } Node q = p.next; if (q == null) { if (p.prev == p) return; activeSucc = p; isLast = true; break; } else if (p == q) return; else p = q; } // TODO: better HOP heuristics // 到这里可以将前继和后继相连了，也就是删除x，但是还可以优化一下 // 只有当前继和后继之间有好几个节点时才进行处理，否则不处理，这样 // 做是为了能够一次性删除多个节点，可以理解为批处理改善性能 if (hops < HOPS // always squeeze out interior deleted nodes // 但是有一种例外，就是当x是队列内部的节点时，即使 // 前继和后继中只有x这一个节点，都进行删除操作 && (isFirst | isLast)) return; // Squeeze out deleted nodes between activePred and // activeSucc, including x. // 这里就是将前继和后继相连的两个函数，也就是实际的unlink操作 skipDeletedSuccessors(activePred); skipDeletedPredecessors(activeSucc); // Try to gc-unlink, if possible // 上面unlink完后，进一步判断是否要对x进行gc-unlink处理 // 前面提到过，只有当x位于端点才进行gc-unlink，先做一些检查，例如看x是不是isFirst // 当然由于是并发的，因此本次检查即使发现x位于端点，后面x也可能变成不是端点， // 因此这个检查只是一种优化而已，因此去掉检查算法也不会错，但是可能性能变差 if ((isFirst | isLast) && // Recheck expected state of predecessor and successor (activePred.next == activeSucc) && (activeSucc.prev == activePred) && (isFirst ? activePred.prev == null : activePred.item != null) && (isLast ? activeSucc.next == null : activeSucc.item != null)) { // 前面的讨论提到过，进行gc-link前，需要将head，和tail // 放到安全的位置，这两个函数就是干这件事的 // 稍后看下是如何处理的 updateHead(); // Ensure x is not reachable from head updateTail(); // Ensure x is not reachable from tail // Finally, actually gc-unlink // 最后进行gc-unlink，如果x在端点处，将x的prev或者next指向哨兵，否则指向自身 // 当然也可以不指向哨兵，都指向自身，但是毕竟x是从队列端点出队的，让x指向哨兵可以 // 保留这一信息，有些操作可以利用这个信息 x.lazySetPrev(isFirst ? prevTerminator() : x); x.lazySetNext(isLast ? nextTerminator() : x); } } }
删除头尾节点：
前面说过，对于头尾节点，不进行unlink处理，这样该函数直接返回即可，但是其实可以顺便检查一下头节点后面的节点是否需要unlink，官方实现中就是检查头节点后面的节点是否可以进行unlink，如果可以就进行后面节点的unlink操作：
private void unlinkFirst(Nodefirst, Node next) { // assert first != null; // assert next != null; // assert first.item == null; for (Node o = null, p = next, q;;) { // 找到了头节点的item非null的后继p if (p.item != null || (q = p.next) == null) { // 当后继与头节点之间的距离大于1，也就是o不为null，对o进行unlink处理， // 队列的状态可能是：first<->节点n(item为null)<->节点o(item为null)<->p // 进行unlink后变成：first<->p (中间两个item为null的节点被unlink) // 注意：此时节点o和n可能还有指针指向first或者p，上面没有画出来 // 遇到冲突时，直接返回不做处理，这同unlink()函数中的道理是一样的 if (o != null && p.prev != p && first.casNext(next, p) ) { // unlink skipDeletedPredecessors(p); // 最后对o进行gc-unlink处理来解除其对队列节点的引用（指针），对n // 也可以进行gc-unlink，不过没必要，gc-unlink只需要少量的运行来 // 保证长的节点引用链偶尔被打断即可 // 这里的gc-unlink的检查逻辑同unlink()函数类似，不再讨论 if (first.prev == null && (p.next == null || p.item != null) && p.prev == first) { updateHead(); // Ensure o is not reachable from head updateTail(); // Ensure o is not reachable from tail // Finally, actually gc-unlink o.lazySetNext(o); o.lazySetPrev(prevTerminator()); } } return; } // 遇到冲突，直接返回 else if (p == q) return; else { // 继续找有效的后继 o = p; p = q; } } }
到这里还剩两个函数skipDeletedSuccessors(activePred)和updateHead():
// 将x与其有效前继相连，有效的前继包括item不为null的节点，以及头节点 private void skipDeletedPredecessors(Nodex) { // 如果x被其他的线程删除了，那么直接返回，因为此时没必要将 // x留在队列中，也就是没必要将其和有效前继相连了 whileActive: do { Node prev = x.prev; // assert prev != null; // assert x != NEXT_TERMINATOR; // assert x != PREV_TERMINATOR; Node p = prev; // 找有效前继 findActive: for (;;) { // 找到了有效前继 if (p.item != null) break findActive; Node q = p.prev; if (q == null) { // 遇到前哨兵节点，表明发生冲突，跳到最外面的循环重来一遍 if (p.next == p) continue whileActive; break findActive; } else if (p == q) // 表明发生冲突，跳到最外循环面重来一遍 continue whileActive; else p = q; } // found active CAS target // 尝试将x和有效前继相连，失败表示x的前继发生了 // 变化，重新找有效前继，否则表示成功，返回 if (prev == p || x.casPrev(prev, p)) return; } while (x.item != null || x.next == null); }
private final void updateHead() {
// Either head already points to an active node, or we keep
// trying to cas it to the first node until it does.
Node h, p, q;
// 尝试将head放到安全的位置
restartFromHead:
// 如果h本来就在安全的位置，那么直接返回
while ((h = head).item == null && (p = h.prev) != null) {
for (;;) {
// 将head放到队头
if ((q = p.prev) == null ||
(q = (p = q).prev) == null) {
// It is possible that p is PREV_TERMINATOR,
// but if so, the CAS is guaranteed to fail.
// 注意p可能是队头，也可能是前哨兵节点，但是根据不变式2，如果p是前哨
// 兵节点，表示发生竞争，head一定会发生变化，也就是cas操作保证会失败
// 想一想head为什么一定会发生变化?（答案在unlink函数里）
if (casHead(h, p))
return; // 成功则返回
else
// cas失败则重新读取head，回到restartFromHead进行处理
continue restartFromHead;
}
else if (h != head)
// 如果head已经发生变化，那么本次寻找很可能找不到队头，所以直接
// 回到restartFromHead重新读取head重新开始
continue restartFromHead;
else
// 继续找队头
p = q;
}
}
}
unlink()实现后，出栈代码如下，根据不变式容易写出：
public E pollFirst() {
for (Node p = first(); p != null; p = succ(p)) {
E item = p.item;
if (item != null && p.casItem(item, null)) {
unlink(p);
return item;
}
}
return null;
}
上面的fisrt()就是从head出发找队头的代码，succ()是找后继的代码，根据不变式也容易写出：?待更新?
实现的一些细节：
1，volatile写比volatile读代价大得多，因此实现上尽量减少volatile写，相应的volatile读可能会增多
2，java的每一次volatile写都会将线程中的所有volatile变量写回到主存
3，java的每一次volatile读都会将主存中的所有volatile变量写回到线程空间
基于2和3可以利用一些技巧来减少一些主存和线程内存之间的数据移动，例如假设有a,b两个volatile变量，某个线程的一次操作中顺序执行a=x,b=y，并且其他线程只有在确保b被复制y后才会读取a的值，那么对a的写可以使用普通写，然后对b使用volatile写将a和b的值同时更新到主存，这样其他线程只要读取到b的新值那么也能读取到a的新值。
官方文档翻译
。由于该实现技术是扩展自ConcurrentLinkedQueue，因此理解ConcurrentLinkedQueue的实现是理解该类实现的前提。
。该类的数据结构为一个双端队列，并且该队列的实现是GC-robust的（意思是被删除节点占用的内存会"及时"得到释放）。该实现通过两种技术来尽量减少volatile写操作：跳跃式移动head或者tail，对同一地址混合non-volatile和volatile操作。
。node包含item并且连接到前继（prev）和后继（next）node:
class Node
。node p被认为是"live"的如果它包含一个non-null的item (p.item != null)，当item被CAS为null后，该item就从集合中被删除了。
。任何时候，队列中有且只有一个"first" node，该node的pre为null，从任一live的node不断往前遍历将会被first node截停。同样的，队列中有且只有一个next为null的"last" node。first和last node可能不是 live node，first和last node总是互相可达的。
。添加一个item到集合就是将包含该item的一个node CAS到first node的prev或者last node的next处，该node自动的成为一个live node。
。node 被认为是"active"的，如果该节点是live node，first node或者last node。active node不可以unlink。
。node被"self-link"如果他的next或者prev指向自身：p.prev = p 或者 p.next = p。self-link用于unlink处理，active node永远不可self-link。
。node p 是 active 的当且仅当：p.item != null || (p.prev == null && p.next != p) || (p.next == null && p.prev = p)
。该双端包含一个head和一个tail节点，head和tail节点是first和last节点的近似，从head节点出发不断往prev遍历一定可以到达first node，tail同理。注意：head和tail有可能指向一个unlink的node，此时从live node出发将可能无法到达head或tail。
。删除节点的过程有3个阶段："logical deletion"，"unlinking"以及"gc-unlinking"
1，"logical deletion"：item被CAS为null
2，"unlinking"：节点将无法从active node到达，最后可以被GC回收。注意：迭代器可能无限期持有该节点（此时GC将无法回收该节点）。虽然unlinking node只是一种优化，但是却非常重要。任何时候，从first node和从last node出发遍历队列会获得相同的live node集合，不过这对"logical deletion"的node不成立，这样的node可能只能在一个方向上被遍历到。
3，"gc-unlinking"：gc unlinking是对unlinking的进一步强化，无法从gc unlinking的node到达active node。这样如果后续删除active node时，GC能更好的回收被删除的active node。这就是"GC robust"的关键。注意：迭代器可以无限期的持有该节点，不过不同于unlinked节点，该节点将无法从head或者tail到达。
。使队列"GC-robust"可以消除保守GC回收器的无限内存驻留的问题，而且也可以改善分代GC的表现。
。当一个node在队头或队尾出队时，我们希望能断开它与active node之间的连接，我们改进self-links这种在其他并发集合中行之有效的技术来到达此目的。具体来说，通过将node的prev和next指向特定的节点来表示该节点off-the-list-at-one-end(从队头或队尾出队)。这只是一种近似，但足够保持遍历过程中的性质（不变式）。比如，我们保证一次遍历永远不会visit同一个node两次，但是不保证遍历到队列端点后是否能观测到后续添加在队列端点的节点。安全的gc-unlinking节点很有挑战，因为任何节点都可能被一直持有（比如被迭代器持有）。我们必须保证被head和tail指向的节点永远不会gc-unlinked，因为需要保证任何时候都可以从head/tail出发遍历整个队列。gc-unlinking大大增加了该实现的复杂程度。
。因为unlinking和gc-unlinking对于正确运行算法来说不是必要的，因此针对队列操作的频繁性可以有不同的实现。因为volatile读比CAS操作代价低得多，因此将多个相邻的node作为一个整体gc-unlinking可以节约CAS操作。gc-unlinking可以少量的进行但却任然有效，因为重要的是保证长的deleted节点链可以时不时的被打断。
。当p.next == p时意味着需要重新从first node出发（可以通过head node找到first node），当p.next == null && p.prev == p时，意味着此时遍历结束并且p节点是一个static fianl的dummy节点，称之为NEXT_TERMINATOR，注意该节点不是队列最端点的active node。当遍历到这样一个TERMINATOR节点时结束遍历对只读遍历来说已经足够，也就是说对于只读遍历，终止条件可以是p.next==null。但当我们需要找到最端点的active node时，比如当enqueue一个新节点时，如果到达了终止节点，那么需要重新从tail出发进行遍历。
。该现实是方向对称的，也就是说队列的头和尾具有相同的属性和功能
。我们认为（没有完全充分的证明）所有单个元素的出队操作（addFirst, peekLast, pollLast）是linearizable的（什么是linearizable可以参考https://www.modb.pro/db/138175）。但是，一些操作的组合不是linearizable的。具体来说，当addFirst(A)和一个正在移除B的pollFirst()操作发生竞争时，对于一个正在遍历队列的观察者来说，他可能首先观测到A B C然后又观测到A C，尽管此时并没有发生中间元素的remove操作，不过，由于迭代器只保证弱一致性，所以这是合理的。（关于强，顺序，弱一致性可以参考https://blog.csdn.net/chao2016/article/details/81149674）
。该类相对于ConcurrentLInkedQueue增加了约40%的运行代价。
