Java Queue vs. Deque

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?

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

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 deque-specific methods for inserting and extracting elements from specific sides of the deque. See the Deque interface article linked above for an overview of these 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?

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

Iteration

Queue, and thus also Deque, extend Collection and thus implement 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);
}

Both data structures are traversed by the iterator from the beginning (head) to the end (tail), as the output of the small example shows:

Queue: 
A
B
C

Deque: 
A
B
C

Deque has an additional descendingIterator() method that can be used to traverse the elements in the opposite direction – that is, from the end to the beginning:

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

Summary

This article taught you the differences between the data structures “deque” and “queue” and the corresponding Java interfaces.