利用Atomic原子引用,采用CAS的方式,实现线程安全的链表栈的实现
关键点
关键在于用
AtomicReference原子类包装栈顶节点,在更改新的栈顶节点的时候,判断原子引用的栈顶是否还是之前获取时的栈顶,如果不是则重新通过AtomicReference获取栈顶。
关键代码
headReference.compareAndSet(oldHead, newHead)
// TODO 这是线程安全的版本
public class MyStack2 {
class Node{
int value;
Node next;
}
// TODO 这个在堆中是线程共享的
private final AtomicReference<Node> headReference = new AtomicReference<>();
// 弹出
public int pop(){
Node oldHead;
Node newHead;
do{
oldHead = headReference.get();
if (oldHead == null){
throw new EmptyStackException();
}
newHead = oldHead.next; // 这里不需要将oldHead.next置null,也不能置空,可能会出错
// cas设置新的栈顶
}while (!headReference.compareAndSet(oldHead, newHead));
return oldHead.value;
}
// 压栈
public void push(int value){
Node node = new Node();
node.value = value;
Node oldHead;
// TODO 采用CAS的方式
// 先获取栈顶,将新节点指向栈顶,如果栈顶还是原来的栈顶,则将新节点设置为栈顶,否则重新获取栈顶
do{
oldHead = headReference.get();
node.next = oldHead;
// 将node置为新的head
// headReference只是用来存放head的
// 如果headReference中的值还是oldHead,则将node放入headReference作为新的head
// 如果不成功,重新获取oldHead
}while (!headReference.compareAndSet(oldHead, node));
}
// 查看栈顶
public int peek(){
Node head = headReference.get();
if (head == null){
throw new EmptyStackException();
}
return head.value;
}
}
图解CAS压栈push操作
第一步
oldHead = headReference.get();
第二步
node.next = oldHead;
第三步,CAS设置新的headReference
headReference.compareAndSet(oldHead, node)