# 非阻塞算法（Lock-Free）的实现

## 非阻塞的栈

```public class Node<E> {
public final E item;
public Node<E> next;

public Node(E item){
this.item=item;
}
}```

```public class ConcurrentStack<E> {

AtomicReference<Node<E>> top= new AtomicReference<>();

public void push(E item){
Node<E> newNode= new Node<>(item);
Node<E> oldNode;
do{
oldNode=top.get();
newNode.next= oldNode;
}while(!top.compareAndSet(oldNode, newNode));
}

public E pop(){
Node<E> oldNode;
Node<E> newNode;
do {
oldNode = top.get();
if(oldNode == null){
return null;
}
newNode=oldNode.next;
}while(!top.compareAndSet(oldNode, newNode));
return oldNode.item;
}

}```

## 非阻塞的链表

```public class LinkedNode<E> {
public final E item;

this.item=item;
this.next=new AtomicReference<>(next);
}
}```

```public class LinkedQueue<E> {
private final AtomicReference<LinkedNode<E>> tail= new AtomicReference<>(nullNode);

public boolean put(E item){
while (true){
if(currentTail == tail.get()){
if (tailNext != null) {
//有其他的线程已经插入了一个节点，但是还没有将tail指向最新的节点
tail.compareAndSet(currentTail, tailNext);
}else{
//没有其他的线程插入节点，那么做两件事情：1. 插入新节点，2.将tail指向最新的节点
if(currentTail.next.compareAndSet(null, newNode)){
tail.compareAndSet(currentTail, newNode);
}
}
}
}
}
}```