Queue Implementations in Java – Which One to Use?
April 26, 2022This 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.
| Class | Base data structure | Thread- safe? | Blocking/ non-blocking | Fairness policy | Bounded/ unbounded | Iterator type |
|---|---|---|---|---|---|---|
| ConcurrentLinkedQueue | Linked list | Yes (optimistic locking through compare-and-set) | Non-blocking | — | Unbounded | Weakly consistent¹ |
| PriorityQueue | Min-heap (stored in an array) | No | Non-blocking | — | Unbounded | Fail-fast² |
| LinkedBlockingQueue | Linked list | Yes (pessimistic locking with two locks) | Blocking | Not available | Bounded | Weakly consistent¹ |
| ArrayBlockingQueue | Array | Yes (pessimistic locking with one lock) | Blocking | Optional | Bounded | Weakly consistent¹ |
| PriorityBlockingQueue | Min-heap (stored in an array) | Yes (pessimistic locking with one lock) | Blocking (nur dequeue) | Not available | Unbounded | Weakly consistent¹ |
| DelayQueue | Priority queue | Yes (pessimistic locking with one lock) | Blocking (nur dequeue) | Not available | Unbounded | Weakly consistent¹ |
| SynchronousQueue | Stack (implemented with a linked list) | Yes (optimistic locking through compare-and-set) | Blocking | Optional | Unbounded | The iterator is always empty. |
| LinkedTransferQueue | Linked list | Yes (optimistic locking through compare-and-set) | Blocking (only transfer and dequeue) | Not available | Unbounded | Weakly 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.
ConcurrentLinkedQueueas a thread-safe, non-blocking, and unbounded queue.ArrayBlockingQueueas a thread-safe, blocking, bounded queue if you expect low to medium contention between producer and consumer threads.LinkedBlockingQueueas 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:
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 HappyCoders.eu newsletter.