Java 实现LockFreeQueue

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
  private AtomicReference<Node> head;
  private AtomicReference<Node> tail;

  /**
   * Create a new object of this class.
   */
  public LockFreeQueue() {
    Node sentinel = new Node(null);
    head = new AtomicReference<Node>(sentinel);
    tail = new AtomicReference<Node>(sentinel);
  }
  /**
   * Enqueue an item.
   * @param value Item to enqueue.
   */
  public void enq(T value) {
    // try to allocate new node from local pool
    Node node = new Node(value);
    while (true) {               // keep trying
      Node last = tail.get();    // read tail
      Node next = last.next.get(); // read next
      // are they consistent?
      if (last == tail.get()) {
        if (next == null) {     // was tail the last node?
          // try to link node to end of list
          if (last.next.compareAndSet(next, node) {
            // enq done, try to advance tail
            tail.compareAndSet(last, node);
            return;
          }
        } else {                // tail was not the last node
          // try to swing tail to next node
          tail.compareAndSet(last, next);
        }
      }
    }
  }
  /**
   * Dequeue an item.
   * @throws queue.EmptyException The queue is empty.
   * @return Item at the head of the queue.
   */
  public T deq() throws EmptyException {
    while (true) {
      Node first = head.get();
      Node last = tail.get();
      Node next = first.next.get();
      // are they consistent?
      if (first == head.get()) {
        if (first == last) {    // is queue empty or tail falling behind?
          if (next == null) {   // is queue empty?
            throw new EmptyException();
          }
          // tail is behind, try to advance
          tail.compareAndSet(last, next);
        } else {
          T value = next.value; // read value before dequeuing
          if (head.compareAndSet(first, next)) {
            return value;
          }
        }
      }
    }
  }
  /**
   * Items are kept in a list of nodes.
   */
  public class Node {
    /**
     * Item kept by this node.
     */
    public T value;
    /**
     * Next node in the queue.
     */
    public AtomicReference<Node> next;

    /**
     * Create a new node.
     */
    public Node(T value) {
      this.next  = new AtomicReference<Node>(null);
      this.value = value;
    }
  }