java - java中的非阻塞栈

Question

有人可以帮助我编写一个非阻塞、无锁的 stack实现。它在 Sun java 实现中吗？

我试图Stack通过在整个堆栈数据结构上放置一个全局锁来编写一个线程安全的（这很昂贵），但似乎可以编写一个非阻塞、无锁的 堆栈。

如果一个算法是无锁且不受死锁的，则该算法称为非阻塞算法。

Answer 1

public class MyConcurrentStack<T> {

    private AtomicReference<Node> head = new AtomicReference<Node>();

    public MyConcurrentStack() {
    }

    public void push(T t) {
        if (t == null) {
            return;
        }
        Node<T> n = new Node<T>(t);
        Node<T> current;

        do {
            current = head.get();
            n.setNext(current);
        } while (!head.compareAndSet(current, n));
    }

    public T pop() {
        Node<T> currentHead = null;
        Node<T> futureHead = null;
        do {
            currentHead = head.get();
            if (currentHead == null) {
                return null;
            }
            futureHead = currentHead.next;
        } while (!head.compareAndSet(currentHead, futureHead));

        return currentHead.data;
    }

    /**
     *
     * @return null if no element present else return a element. it does not
     * remove the element from the stack.
     */
    public T peek() {
        Node<T> n = head.get();
        if (n == null) {
            return null;
        } else {
            return n.data;
        }
    }

    public boolean isEmpty() {
        if (head.get() == null) {
            return true;
        }
        return false;
    }

    private static class Node<T> {

        private final T data;
        private Node<T> next;

        private Node(T data) {
            this.data = data;
        }

        private void setNext(Node next) {
            this.next = next;
        }
    }
}

Answer 2

并发堆栈java第一个谷歌结果

队列

java.util.concurrent ConcurrentLinkedQueue类提供了一个高效的可扩展线程安全非阻塞 FIFO 队列。java.util.concurrent 中的五个实现支持扩展 BlockingQueue接口，它定义了 put 和 take 的阻塞版本：LinkedBlockingQueue、ArrayBlockingQueue、 SynchronousQueue、PriorityBlockingQueue和 DelayQueue. 不同的类涵盖了生产者-消费者、消息传递、并行任务和相关并发设计的最常见使用上下文。BlockingDeque 接口扩展了 BlockingQueue 以支持 FIFO 和 LIFO（基于堆栈）操作。LinkedBlockingDeque 类提供了一个实现。