非阻塞同步算法

栈顶为一序列

[java]
public class ConcurrentStack {
AtomicReference> top = new AtomicReference>();

public void push(E item){
Node newHead = new Node(item);
Node oldHead = null;
do{
oldHead = top.get();
newHead.next = oldHead;
}while(!top.compareAndSet(oldHead, newHead));
}

public E pop(){
Node newHead = null;
Node oldHead = null;
do{
oldHead = top.get();
if(oldHead == null){
return null;
}
newHead = oldHead.next;
}while(!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}

private static class Node{
public final E item;
public Node next;
public Node(E item){
this.item = item;
}
}
}

public class ConcurrentStack {
AtomicReference> top = new AtomicReference>();

public void push(E item){
Node newHead = new Node(item);
Node oldHead = null;
do{
oldHead = top.get();
newHead.next = oldHead;
}while(!top.compareAndSet(oldHead, newHead));
}

public E pop(){
Node newHead = null;
Node oldHead = null;
do{
oldHead = top.get();
if(oldHead == null){
return null;
}
newHead = oldHead.next;
}while(!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}

private static class Node{
public final E item;
public Node next;
public Node(E item){
this.item = item;
}
}
}

Michael Scott 1996

队尾和尾部节点两个序列

[java]
public class ConcurrentLink {

private final Node dummy = new Node(null, null);

private final AtomicReference> head =
new AtomicReference>(dummy);
private final AtomicReference> tail =
new AtomicReference>(dummy);

public boolean push(E item){
Node newNode = new Node(item, null);
while(true){
Node curTail = tail.get();
Node tailNext = curTail.next.get();
if(curTail == tail.get()){
if(tailNext != null){
tail.compareAndSet(curTail, tailNext);
}else{
if(curTail.next.compareAndSet(null, newNode)){
tail.compareAndSet(curTail, newNode);
return true;
}
}
}
}
}

private static class Node{
final E item;
final AtomicReference> next;

public Node(E item, Node next){
this.item = item;
this.next = new AtomicReference>(next);
}
}

}