Queue vs. Deque in Java: What’s the Difference?

In this article, you will learn:

• What are the differences between the deque and queue data structures?
• How do the Java interfaces Queue and Deque differ?
• What has changed since Java 21 with SequencedCollection?

Let’s start with the data structures.

Difference between Queue and Deque

A queue is a data structure that works according to the FIFO principle: Elements put into the queue first are taken out first. Elements are inserted at the end of the queue (also called “tail”) and removed at the beginning (“head”):

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

Deque (pronounced “deck”) stands for “double-ended queue”, i.e., a queue with two sides. With a deque, elements can be inserted into and removed from both sides:

A deque is an extension of a queue and can also be used as such. However, it is not limited to FIFO functionality. It can also be used as a LIFO data structure – i.e., as a stack – by inserting and removing elements on only one side.

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

Difference between Java Deque and Queue

This section describes the differences between the Java interfaces java.util.Queue and java.util.Deque.

Deque Extends Queue and SequencedCollection

Deque (→ all details about the Deque interface) was introduced in Java 6 as an extension of Queue (→ all details about the Queue interface), which was introduced in Java 5.

Deque extends Queue with methods that insert and remove elements specifically at the head or at the tail. See the Deque interface article linked above for an overview of these methods.

Since Java 21, Deque also extends the SequencedCollection interface. It guarantees a defined order of its elements and defines uniform methods for accessing both ends – getFirst(), getLast(), addFirst(), addLast(), removeFirst(), and removeLast(). Deque has had these methods since Java 6 – JEP 431 promoted them from there into the new interface, hence their names. What is new is reversed(), which returns a reverse-ordered view of the elements.

Queue does not extend SequencedCollection: A queue only defines which element is at the head, not the order of all its elements. In a PriorityQueue, for example, the head is the element with the highest priority; the remaining elements have no defined order – so there is no “last” element that getLast() could return.

The following diagram shows the inheritance relationships of the four interfaces, each with the Java version that introduced it and its most important methods:

Implementations and Performance

Both interfaces offer numerous implementations with different characteristics. You can find out which one you should use here:

• Which Queue implementation should I use?
• Which Deque implementation should I use?

Performance depends on the implementation, not on the interface. For single-threaded applications, I recommend ArrayDeque as a queue as well as a deque; the two articles linked above tell you which implementation to pick for access from multiple threads.

Since Deque inherits from Queue, any deque implementation can also be used as a queue.

Iteration

Queue – and thus also Deque – extends Collection and thus implements the Iterable interface. Therefore, we can iterate over both data structures within a for loop:

Queue<String> queue = new ConcurrentLinkedQueue<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");

System.out.println("Queue:");
for (String s : queue) {
  System.out.println(s);
}

Deque<String> deque = new ArrayDeque<>();
deque.offerLast("A");
deque.offerLast("B");
deque.offerLast("C");

System.out.println("\nDeque:");
for (String s : deque) {
  System.out.println(s);
}

The iterator of a deque is guaranteed to traverse the elements from the beginning (head) to the end (tail). For a queue, that holds only for FIFO implementations such as ConcurrentLinkedQueue or LinkedList; the iterator of a PriorityQueue, in contrast, returns the elements in no particular order. The output of the example:

Queue:
A
B
C

Deque:
A
B
C

Since Java 21, deque.reversed() returns a reverse-ordered view of the deque that you can iterate over directly:

for (String s : deque.reversed()) {
  System.out.println(s);
}

The output:

C
B
A

In older Java versions, the descendingIterator() method does the same job:

for (Iterator<String> iterator = deque.descendingIterator(); iterator.hasNext(); ) {
  String s = iterator.next();
  System.out.println(s);
}

Summary

The following table contrasts the differences between queue and deque – the first three rows cover the data structures, the remaining rows the Java interfaces:

	Queue	Deque
Principle	FIFO	FIFO and LIFO
Insertion	at the tail only	at both ends
Removal	at the head only	at both ends
Java interface since	Java 5	Java 6
Extends	Collection	Queue and, since Java 21, SequencedCollection
Iteration order	depends on the implementation	guaranteed head to tail, reversed via reversed()
Typical implementations	LinkedList, PriorityQueue, ConcurrentLinkedQueue, ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue	ArrayDeque, LinkedList, ConcurrentLinkedDeque, LinkedBlockingDeque

If all you need is FIFO, the Queue interface is enough. As soon as you work at both ends or want to iterate backward, use Deque.