使用 Treiber 算法（Treiber,1986）构造的非阻塞栈_综合

读《Java并发编程实战》笔记。

import java.util.concurrent.atomic.AtomicReference;/*** 使用 Treiber 算法（Treiber,1986）构造的非阻塞栈* <p>** @author hyl* @version v1.0: ConcurrentStack.java, v 0.1 2020/10/22 17:18 $*/
public class ConcurrentStack<E> {
    AtomicReference<Node<E>> top = new AtomicReference<>();public void push(E item) {
    Node<E> newHead = new Node<>(item);Node<E> oldHead;do {
    oldHead = top.get();newHead.next = oldHead;} while (!top.compareAndSet(oldHead, newHead));}public E pop() {
    Node<E> oldHead;Node<E> newHead;do {
    oldHead = top.get();if (oldHead == null)return null;newHead = oldHead.next;} while (!top.compareAndSet(oldHead, newHead));return oldHead.item;}private static class Node<E> {
    public final E item;public Node<E> next;public Node(E item) {
    this.item = item;}}
}

说明：

ConcurrentStack 中给出了如何通过原子引用来构建栈的示例。

栈是由Node元素构成的一个链表，其中栈顶作为根节点，并且在每个元素中都包含了一个值以及指向下一个元素的连接。

push 方法创建一个新的节点，该节点的 next 域指向当前的栈顶，然后使用 CAS 把这个新节点放入栈顶。如果在开始插入节点时，位于栈顶的节点没有发生变化，那么 CAS 就会成功，如果栈顶节点发生了变化，那么 CAS 就会失败，而 push 方法会根据栈的当前状态来更新节点，并且再次尝试。

无论那种情况，在 CAS 执行完成后，栈仍会处于一致的状态。