Stack, Queue, Deque in Java

Sooner or later, Java developers have to deal with the abstract data type queue, deque, and stack. In the stack, queue and deque tutorials, you will find answers to the following questions:

• How do the queue, deque, and stack data structures work in general?
• How do they differ?
• How do the Java interfaces and classes Stack, Queue and Deque differ?
• Which queue, deque, and stack implementations are provided by the JDK?
• Which of the numerous implementations are suitable for which purposes?
• How to implement queues, deques and stacks yourself?

You can find all code examples in the “Java Collections Guide” GitHub repository.

Data structures: What are stacks, queues, and deques?

A stack is a list of elements in which elements are inserted (“stacked”) and removed on the same side (in representations classically at the top):

For more details, see the main article about the stack data structure.

A queue is a list of elements where elements are inserted on one side and removed in the same order on the other side:

You can learn everything about queues in the main article about the queue data structure.

A deque (Double-ended queue, pronounced “deck”) is a list of elements where the elements can be inserted and removed both on one side and on the other:

For details, see the main article about the deque data structure.

How do Stack, Queue, and Deque Differ?

The differences between the respective data structures are explained in the following articles:

• Differences between deque and stack
• Differences between queue and deque
• Differences between stack and queue

What Java Implementations Are Available, and Which Should You Use?

The usage recommendations are based on the characteristics of the JDK queue and deque implementations, which are described in more detail in the linked articles.

The following are my recommendations for general purpose use:

• Use ArrayDeque for single-threaded applications.
• ConcurrentLinkedQueue and ConcurrentLinkedDeque as thread-safe, non-blocking, and unbounded queues/deques.
• ArrayBlockingQueue as a thread-safe, blocking, bounded queue, provided you expect little contention between producer and consumer threads.
• LinkedBlockingQueue as a thread-safe, blocking, bounded queue if you expect a rather high contention between producer and consumer threads (it is best to test which implementation is better performing for your use case).
• LinkedBlockingDeque as a thread-safe, blocking, bounded deque.
• ... or the optimized queues of JCTools.

The following queues are for special purposes:

• PriorityQueue and PriorityBlockingQueue to retrieve elements sorted by priority.
• DelayQueue to retrieve elements after a given waiting time.
• SynchronousQueue to transfer elements synchronously from a producer to a consumer.
• LinkedTransferQueue to block a producer thread until the element has been transferred to a consumer thread.