可以看到,尽管1在多线程环境下会产生元素覆盖问题,但是对于最后一个覆盖的线程而言,2的CAS更新是必然会成功的,不管这个CAS更新是由该线程自己执行还是其他线程替他执行,一旦某线程CAS更新成功,其他线程将因CAS失败重新执行for循环。

2.2 链表实现

基于链表实现无锁的栈会更灵活,不用考虑栈扩容或者栈空间满的问题,而且实现同样简单。

/**  * @author: takumiCX  * @create: 2018-08-09  *  * 基于链表实现的无锁的并发栈  **/ public class LockFreeLinkedStack<E> implements LockFreeStack<E>{      //栈顶指针     AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();      /**      * @param e 入栈元素      * @return true:入栈成功 false:入栈失败      */     public boolean push(E e) {          //构造新结点         Node<E> newNode = new Node<E>(e);          //死循环,保证CAS失败重试后能入栈成功         for (; ; ) {             //当前栈顶结点             Node<E> curTopNode = top.get();             //新结点的next指针指向原栈顶结点             newNode.next = curTopNode;             //CAS更新栈顶指针             if (top.compareAndSet(curTopNode, newNode)) {                 return true;             }         }      }       /**      *      * @return 返回栈顶结点中的值,若栈为空返回null      */     public E pop() {          //死循环,保证出栈成功         for (; ; ) {             //当前栈顶结点             Node<E> curTopNode = top.get();             //栈为空,返回null             if (curTopNode == null) {                 return null;             } else {                 //获得原栈顶结点的后继结点                 Node<E> nextNode = curTopNode.next;                 //CAS更新栈顶指针                 if (top.compareAndSet(curTopNode, nextNode)) {                     return curTopNode.item;                 }             }         }     }       //定义链表结点     private static class Node<E> {          public E item;          public Node<E> next;          public Node(E item) {             this.item = item;         }     } } 

由定义可知,该链表为单链表,且不带哨兵。为了操作方便,新增结点的插入采用头插法。如下图所示:

因为栈顶元素的更新依赖于前值(我们要保证更新栈顶指针前没有其他线程对其进行更改),故而使用原子引用,基于原子引用的CAS算法可以保证只有当更新前的引用为预期值时,当前更新才能成功(注意栈顶指针的初始化方式,至于为何不能直接给top赋值为null后面队列部分会解释)。其入栈出栈流程也十分简单,仅需对栈顶指针top进行CAS同步。

• 入栈时:1.获取当前栈顶结点 2.新结点的next指针指向获取的栈顶结点 3.CAS更新栈顶指针。CAS竞争失败的线程将会重复这一流程。
• 出栈时:1. 获取当前栈顶结点 2.若栈顶结点为null,说明栈为空,返回null,否则CAS更新栈顶指针为原栈顶结点的下一个结点 3.返回原栈顶结点的元素 。CAS失败的线程将会重复这一流程。

2.3 性能测试