读《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 执行完成后，栈仍会处于一致的状态。