非阻塞算法-栈

上一节我们以计数器作为例子描述了非阻塞算法，这一节我们拿一个稍微复杂一点的数据结构栈来讲述非阻塞算法的实践应用。
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指向旧的栈头即可，如果失败的话说明其他线程已经修改了栈头节点，需要重新循环回到第一步继续获取新的栈头进行操作直到成功为止。在竞争十分严重的情况下，可能会失败多次，执行多次循环。