/**
 * Inserts the specified element at the tail of this queue.
 *
 * @return {@code true}  (as specified by {@link Collection#add})
 * @throws NullPointerException if the specified element is null
 */
public boolean add(E e) {
    return offer(e);
}

/**
    * Inserts the specified element at the tail of this queue.
    *
    * @return {@code true} (as specified by {@link Queue#offer})
    * @throws NullPointerException if the specified element is null
    */
   public boolean offer(E e) {
       if (e == null) throw new NullPointerException();
       Node<E> n = new Node<E>(e);
       retry:
       for (;;) {
           Node<E> t = tail;
           Node<E> p = t;
           for (int hops = 0; ; hops++) {
               // 1
               Node<E> next = succ(p);
               if (next != null) {
                   // 2
                   if (hops > HOPS && t != tail)
                       continue retry;
                   // 3
                   p = next;
               } else if (p.casNext(null, n)) {// 4
                   // 5
                   if (hops >= HOPS)
                       casTail(t, n); // Failure is OK.
                   return true;   
               } else {// 6
                   p = succ(p);
               }
           }
       }
   }

/**
 * Returns the successor of p, or the head node if p.next has been
 * linked to self, which will only be true if traversing with a
 * stale pointer that is now off the list.
 */
 final Node<E> succ(Node<E> p) {
     Node<E> next = p.getNext();
     // 1
     return (p == next) ? head : next;
 }

public E poll() {
        Node<E> h = head;
        Node<E> p = h;
        for (int hops = 0; ; hops++) {
            // 1
            E item = p.getItem();
            // 2
            if (item != null && p.casItem(item, null)) {
                if (hops >= HOPS) {
                    Node<E> q = p.getNext();
                    // 3
                    updateHead(h, (q != null) ? q : p);
                }
                return item;
            }
            // 4
            Node<E> next = succ(p);
            // 5
            if (next == null) {
                updateHead(h, p);
                break;
            }
            p = next;
        }
        // 6
        return null;
    }

/**
 * Try to CAS head to p. If successful, repoint old head to itself
 * as sentinel for succ(), below.
 */
 final void updateHead(Node<E> h, Node<E> p) {
     if (h != p && casHead(h, p))
        // 1
         h.lazySetNext(h);
 }

public E peek() {
    Node<E> h = head;
    Node<E> p = h;
    E item; 
    for (;;) {
        item = p.getItem();
        if (item != null)
            break;
        Node<E> next = succ(p);
        if (next == null) {
            break;
        }
        p = next;
    }
    updateHead(h, p);
    return item;
}

/**
 * Returns the first live (non-deleted) node on list, or null if none.
 * This is yet another variant of poll/peek; here returning the
 * first node, not element. We could make peek() a wrapper around
 * first(), but that would cost an extra volatile read of item,
 * and the need to add a retry loop to deal with the possibility
 * of losing a race to a concurrent poll().
 */
 Node<E> first() {
     Node<E> h = head;
     Node<E> p = h;
     Node<E> result;
     for (;;) { 
         E item = p.getItem();
         if (item != null) {
             result = p;
             break;
         }
         Node<E> next = succ(p);
         if (next == null) {
             result = null;
             break;
         }
         p = next;
     }
     updateHead(h, p);
     return result;
 }

/**
* Returns {@code true} if this queue contains no elements.
*
* @return {@code true} if this queue contains no elements
*/ 
public boolean isEmpty() {
    return first() == null;
}

/**
     * Returns the number of elements in this queue.  If this queue
     * contains more than {@code Integer.MAX_VALUE} elements, returns
     * {@code Integer.MAX_VALUE}.
     *
     * <p>Beware that, unlike in most collections, this method is
     * <em>NOT</em> a constant-time operation. Because of the
     * asynchronous nature of these queues, determining the current
     * number of elements requires an O(n) traversal.
     *
     * @return the number of elements in this queue
     */
    public int size() {
        int count = 0;
        for (Node<E> p = first(); p != null; p = succ(p)) {
            if (p.getItem() != null) {
                // Collections.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
            }
        }
        return count;
    }

/**
 * Returns an iterator over the elements in this queue in proper sequence.
 * The returned iterator is a "weakly consistent" iterator that
 * will never throw {@link  java.util.ConcurrentModificationException
 * ConcurrentModificationException},
 * and guarantees to traverse elements as they existed upon
 * construction of the iterator, and may (but is not guaranteed to)
 * reflect any modifications subsequent to construction.
 *
 * @return an iterator over the elements in this queue in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}