Class LockFreeQueue<E>

  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractQueue<E>
          extended by org.amino.ds.lockfree.LockFreeQueue<E>
Type Parameters:
E - type of element in the queue
All Implemented Interfaces:
java.lang.Iterable<E>, java.util.Collection<E>, java.util.Queue<E>

public class LockFreeQueue<E>
extends java.util.AbstractQueue<E>
implements java.util.Queue<E>

This is an implementation of a lock-free FIFO queue data structure. The implementation is according to the paper An Optimistic Approach to Lock-Free FIFO Queues by Edya Ladan-Mozes and Nir Shavit, 2004. To gain a complete understanding of this data structure, please first read this paper, available at:

First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java Concurrency Package. This paper presents a new dynamic-memory lock-free FIFO queue algorithm that performs consistently better than the Michael and Scott queue.

The key idea behind our new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an optimistic doubly-linked list whose pointers are updated using a simple store, yet can be fixed if a bad ordering of events causes them to be inconsistent. It is a practical example of an optimistic approach to reduction of synchronization overhead in concurrent data structures.

Sample performance results here.

The following operations are thread-safe and scalable (but see notes in method javadoc): first, offer, poll, peek

The following operations are not thread-safe: size, iterator

Xiao Jun Dai

Constructor Summary
          default constructor.
LockFreeQueue(java.util.Collection<? extends E> c)
          Constructor with initial collection.
Method Summary
 boolean isEmpty()
 java.util.Iterator<E> iterator()
 boolean offer(E e)
 E peek()
 E poll()
 int size()
Methods inherited from class java.util.AbstractQueue
add, addAll, clear, element, remove
Methods inherited from class java.util.AbstractCollection
contains, containsAll, remove, removeAll, retainAll, toArray, toArray, toString
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Queue
add, element, remove
Methods inherited from interface java.util.Collection
addAll, clear, contains, containsAll, equals, hashCode, remove, removeAll, retainAll, toArray, toArray

Constructor Detail


public LockFreeQueue()
default constructor.


public LockFreeQueue(java.util.Collection<? extends E> c)
Constructor with initial collection.

c - collection for initialization
Method Detail


public boolean isEmpty()

Specified by:
isEmpty in interface java.util.Collection<E>
isEmpty in class java.util.AbstractCollection<E>


public java.util.Iterator<E> iterator()

Specified by:
iterator in interface java.lang.Iterable<E>
Specified by:
iterator in interface java.util.Collection<E>
Specified by:
iterator in class java.util.AbstractCollection<E>


public int size()

Specified by:
size in interface java.util.Collection<E>
Specified by:
size in class java.util.AbstractCollection<E>


public boolean offer(E e)

Specified by:
offer in interface java.util.Queue<E>


public E peek()

Specified by:
peek in interface java.util.Queue<E>


public E poll()

Specified by:
poll in interface java.util.Queue<E>

Copyright © 2008. All Rights Reserved.