Java Collections - Queue

Implementations of Queue

Java provides several implementations of the Queue Interface - each tailored for a particular design requirement.

ConcurrentLinkedQueue

This class provides an unbounded thread-safe FIFO queue based on linked nodes. Iterators of this queue are Thread Safe. It provides for memory consistency. But bulk operations may not be atomic.

PriorityQueue

This class provides a queue that is not FIFO. The elements are ordered based on the priority defined by the natural order or comparison. This class does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so results in ClassCastException). It provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size). It is Not Thread Safe. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.

LinkedBlockingDeque

This class provides an optionally-bounded blocking deque based on linked nodes. The optional capacity bound constructor argument serves as a way to prevent excessive expansion. The capacity, if unspecified, is equal to Integer.MAX_VALUE. Linked nodes are dynamically created upon each insertion unless this would bring the deque above capacity.

ArrayBlockingQueue

This class is a provides a blocking queue backed by an array. The size is fixed and cannot change after it is created. The constructor has an optional parameter for fairness. If this is set to true, it treats waiting threads fairly - granting access in FIFO order. This reduces variability and avoids starvation. But adds overheads and hence reduces throughput.

PriorityBlockingQueue

This class provides an unbounded blocking queue orders elements and supplies blocking retrieval operations. It is logically unbounded, attempted additions will fail only due to resource exhaustion (causing OutOfMemoryError). The priority applies only to the queue methods. The Iterator does not guarantee any particular order. Also, it makes no guarantees about the ordering of elements with equal priority.

SynchronousQueue

This class provides a unique implementation of BlockingQueue with zero capacity. That is, a write should wait for the corresponding read and viceversa. This is very useful in synchronizing between two independent threads. Optionally, you can add fairness policy for the waiting threads.

LinkedTransferQueue

This class provides an unbounded TransferQueue based on linked nodes. Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a LinkedTransferQueue happen-before actions subsequent to the access or removal of that element from the LinkedTransferQueue in another thread.

DelayQueue

This class provides additional functionality to an unbounded blocking queue. You can add a delay to its elements. Sn element can only be taken when its delay has expired. The head of the queue is that Delayed element whose delay expired furthest in the past. If no delay has expired there is no head and poll will return null. Expiration occurs when an element's getDelay(TimeUnit.NANOSECONDS) method returns a value less than or equal to zero. Even though unexpired elements cannot be removed using take or poll, they are otherwise treated as normal elements. For example, the size method returns the count of both expired and unexpired elements. This queue does not permit null elements.

ArrayDeque

This class provides a resizable-array based implementation of the Deque interface. It does not have capacity restrictions. They are Not Thread Safe.

ConcurrentLinkedDeque

This class provides an unbounded concurrent deque based on linked nodes. It is Thread Safe and the Iterators are weakly consistent.

LinkedBlockingDeque

This class provides an optionally-bounded blocking deque based on linked nodes. The Linked nodes are dynamically created upon each insertion.