Java Queue Implementations - Feature ImageJava Queue Implementations - Feature Image
HappyCoders Glasses

Queue Implementations - Which One to Use?

Sven Woltmann
Sven Woltmann
April 26, 2022

This article provides an overview of all Queue implementations available in the JDK, including their characteristics, as well as a decision support for which implementation is best suited for which purpose.

The class names in the following table are linked to that article of the tutorial series in which the respective Queue implementation is explained in detail.

For an explanation of the terms blocking, non-blocking, fairness policy, bounded, and unbounded, see the article about the BlockingQueue interface.

ClassBase data structureThread-
Iterator type
ConcurrentLinkedQueueLinked listYes
(optimistic locking through compare-and-set)
Non-blockingUnboundedWeakly consistent¹
(stored in an array)
LinkedBlockingQueueLinked listYes
(pessimistic locking with two locks)
BlockingNot availableBoundedWeakly consistent¹
(pessimistic locking with one lock)
Blocking OptionalBoundedWeakly consistent¹
(stored in an array)
(pessimistic locking with one lock)
(nur dequeue)
Not availableUnboundedWeakly consistent¹
DelayQueuePriority queueYes
(pessimistic locking with one lock)
(nur dequeue)
Not availableUnboundedWeakly consistent¹
(implemented with a linked list)
(optimistic locking through compare-and-set)
BlockingOptionalUnboundedThe iterator is always empty.
LinkedTransferQueueLinked listYes
(optimistic locking through compare-and-set)
(only transfer and dequeue)
Not availableUnboundedWeakly consistent¹

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

² Fail-fast: The iterator throws a ConcurrentModificationException if elements are added to or removed from the queue during iteration.

When Should You Use Which Queue Implementation?

Using the characteristics of the queue implementations described in the respective articles and summarized in the table above, you can find the proper queue for each use case.

For day-to-day use of general queue implementations, I make the following recommendations:

  • ArrayDeque for single-threaded applications.
  • ConcurrentLinkedQueue as a thread-safe, non-blocking, and unbounded queue.
  • ArrayBlockingQueue as a thread-safe, blocking, bounded queue if you expect low to medium contention between producer and consumer threads.
  • LinkedBlockingQueue as a thread-safe, blocking, bounded queue if you expect high contention between producer and consumer threads (best to test which implementation is more performant for your use case).

Here is the process in the form of a decision tree:

Decision tree Java Queue implementations
Decision tree Java Queue implementations

Optimized MPMC, MPSC, SPMC, and SPSC Queues

All thread-safe queue implementations provided by the JDK can be used in multi-producer-multi-consumer environments. This means that one or more writing threads and one or more reading threads can access the JDK queues concurrently.

With special mechanisms, it is possible to optimize queues so that the overhead for maintaining thread safety is minimized when there is a restriction to one reading and/or one writing thread.

Accordingly, the following four cases are distinguished:

  • Multi-producer-multi-consumer (MPMC)
  • Multi-producer-single-consumer (MPSC)
  • Single-producer-multi-consumer (SPMC)
  • Single-producer-single-consumer (SPSC)

The open-source library JCTools provides highly optimized queue implementations for all four cases.

Summary and Outlook

This article has provided an overview of all Queue implementations available in Java, as well as a decision aid for which cases to use which queue.

In the next parts of this series, I'll show you how to implement queues yourself, starting with implementing a queue with a stack.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the newsletter.