// Non Blocking Queue

class NonBlockingQueue {
  private QueueItem Head;
  private QueueItem Tail;
  ...

NonBlockingQueue() {
     node = new QueueItem()
     node.next.ref = NULL
     this.Head = this.Tail = node
}

public void enqueue(Object value) {
e_1   node = new QueueItem()
e_2   node.value = value
e_3   node.next.ref = NULL
e_4   while(true) { // Keep trying until done
e_5    tail = this.Tail
e_6    next = tail.ref.next
e_7    if (tail == this.Tail) {
e_8     if (next.ref == NULL) {
e_9      if CAS(tail.ref.next, next, <node, next.count+1>) {
e_10       break // Enqueue is done. Exit loop
e_11      }
e_12     } else {
e_13       CAS(this.Tail, tail, <next.ref, tail.count+1>)
e_14     }
e_15    }
e_16   }
e_17   CAS(this.Tail, tail, <node, tail.count+1>)
e_18 }

public Object dequeue() {
  Object result = null
d_1   while(true) {
d_2    head = this.Head
d_3    tail = this.Tail
d_4    next = head.next
d_5    if (head == this.Head) {
d_6     if (head.ref == tail.ref) {
d_7      if (next.ref == NULL) { // is empty?
d_8       return result
d_9      }
d_10      CAS(this.Tail, tail, <next.ref, tail.count+1>)
d_11     } else { // No need to deal with Tail
d_12      result = next.ref.value
d_13      if CAS(this.Head, head, <next.ref, head.count+1>) {
d_14       break // dequeue done
d_15      }
d_16     }
d_17    }
d_18   }
d_19 free(head.ref) // safe to free old dummy node
d_20 return result
d_21
} }

// QueueItem.java
class QueueItem {
    public QueueItem next;
    public Object value;
    ...
}