上一節我們以計數器作為例子描述了非阻塞算法，這一節我們拿一個稍微復雜一點的數據結構棧來講述非阻塞算法的實踐應用。
1.單線程棧

public class SingleThreadStack  implements Stack{    PRivate Node head;    public Node pop() {        if (head == null) {            return null;        }        Node h = head;        head = head.getNext();        h.setNext(null);        return h;    }        @Override    public void push(int value) {        Node node = new Node();        node.setValue(value);        node.setNext(head);        head = node;    }}

出棧即把棧頭彈出，并且把棧頭設為下一個節點，如果棧頭為空，說明棧是空的，直接返回null。入棧時把新入棧節點的next設為原來的棧頭，并且把新的節點設為棧頭。這個棧不是線程安全的，拿出棧來說，如果A、B兩個線程同時出棧，棧中只有2個元素，兩次出棧后棧內元素應該都彈出了，但是如果A、B兩個線程同時執行了head = head.getNext();這條代碼（這條代碼本質是先取出next，再賦值）就可能使得A、B兩個線程兩次出棧操作只出彈出并返回了同一個元素。入棧也是相同的道理。

2.多線程同步棧

public class SynchronizedStack implements Stack{    private SingleThreadStack delegate = new SingleThreadStack();    @Override    public synchronized Node pop() {        return delegate.pop();    }    @Override    public synchronized void push(int value) {        delegate.push(value);    }}

為了更好地說明同步的作用，這里直接把所有棧操作代理給了前文的單線程棧，可以看到因為出棧和入棧都是同步串行操作，就不會出現前面提及的多線程并發操作導致的兩個線程同時操作只出了一個元素的情況。實際是把多線程并發操作排了個隊，先拿到鎖的先操作，后拿到鎖的后操作。

3.無鎖算法棧

public class CasNoLockStack implements Stack {    private CasNode head;    @Override    public CasNode pop() {        for (; ; ) {            CasNode h = head;            // 當前棧是空的            if (h == null) {                return null;            }            CasNode next = h;            if (head.casSet(h, next)) {                h.setNext(null);                return h;            }        }    }    @Override    public void push(int value) {        CasNode node = new CasNode();        node.setValue(value);        for (; ; ) {            CasNode h = head;            if (head.casSet(h, node)) {                node.setNext(h);                return;            }        }    }}

分別從出棧和入棧來說：
出棧時，先在當前線程獲取棧頭賦值給局部變量h，如果h為空，說明當前棧為空棧，直接返回null即可。繼續獲取h的下一個節點next，然后嘗試把棧頭用cas(h,next)方法設置為next節點，這個方法如果返回成功的話，說明已經成功的更新棧頭，那說明h節點是之前最新的棧頭，將h的next節點設置為空并返回即可。這個方法如果返回失敗的話，說明棧頭已經被其他線程修改了，那就重新從最開始的第一步開始循環這個過程直到成功為止，這個循環一定會結束，因為cas操作不成功代表其他線程已經做了出棧操作，那最后要么成功在當前線程出棧，要么其他線程把棧內元素都彈出，當前線程返回null。
接下來說入棧，入棧時先創建新的棧頭節點node，進入循環后，第一步先獲取當前棧頭賦值給局部變量h，用cas(h,node)嘗試把棧頭賦值給新的入棧節點node，如果成功的話說明其他線程沒有修改棧頭，當前線程已經修改棧頭成功，再把新棧頭的next指向舊的棧頭即可，如果失敗的話說明其他線程已經修改了棧頭節點，需要重新循環回到第一步繼續獲取新的棧頭進行操作直到成功為止。在競爭十分嚴重的情況下，可能會失敗多次，執行多次循環。