Deque Data Structure: What Is a Deque (Double-Ended Queue)?

In this tutorial, you will learn about the data structure “deque” (pronounced “deck”):

• What is a deque?
• What operations does a deque provide – and what are they called in Java?
• Which variants of the deque exist?
• What are the applications for deques?
• How expensive are the deque operations?

What Is a Deque?

A deque is a sequence of elements where elements can be inserted and removed both on one side and on the other. Deque stands for “double-ended queue”, i.e., a queue with two ends:

A deque can be used as a queue as well as a stack:

• As a queue (FIFO, first-in-first-out) by inserting elements on one side and removing them on the other side.
• As a stack (LIFO, last-in-first-out) by inserting and removing elements on the same side.

However, we don’t have to limit ourselves to FIFO or LIFO functionality with the deque. We can insert and remove the elements at any time on any side.

Deque Operations

The deque’s operations are “enqueue” and “dequeue” on both sides, analogous to the queue, plus “peek”:

• “Enqueue at front”: inserting an element at the head of the deque
• “Enqueue at back”: inserting an element at the tail of the deque
• “Dequeue at front”: removing an element from the head of the deque
• “Dequeue at back”: removing an element from the tail of the deque
• “Peek at front” and “peek at back”: looking at the element at the head or the tail without removing it (optional)

The dequeue operations cannot remove anything from an empty deque. If a deque has a fixed capacity and is full, the enqueue operations cannot insert anything. Each implementation decides for itself how it reacts – with a special return value or with an exception.

The Deque Operations in Java

The JDK’s Deque interface offers each of the six operations in two variants: one throws an exception if the operation is not possible, the other returns a special value.

Operation	On failure: exception	On failure: return value
Enqueue at front	addFirst()	offerFirst() – false if the deque is full
Enqueue at back	addLast()	offerLast() – false if the deque is full
Dequeue at front	removeFirst()	pollFirst() – null if the deque is empty
Dequeue at back	removeLast()	pollLast() – null if the deque is empty
Peek at front	getFirst()	peekFirst() – null if the deque is empty
Peek at back	getLast()	peekLast() – null if the deque is empty

addFirst() and addLast() throw an IllegalStateException, the other four methods in the middle column a NoSuchElementException. By the way, of the JDK’s deque implementations, only LinkedBlockingDeque can have a capacity limit – all others are never full.

Variants of the Deque

Like the queue, the deque comes in several variants:

• Bounded and blocking deque: A bounded deque has a fixed capacity. A blocking deque makes the calling thread wait until an element is available (when removing) or until there is free space (when inserting). For this, the JDK provides the BlockingDeque interface with its implementation LinkedBlockingDeque.
• Thread-safe, non-blocking deque: Several threads may insert and remove at both sides at the same time. Unlike with the blocking deque, no thread waits: on an empty deque, pollFirst() returns null immediately. For this, the JDK provides the class ConcurrentLinkedDeque.
• Input-restricted and output-restricted deque: The first allows insertion on one side only, the second removal. These two variants come from textbook theory; the JDK has no classes of its own for them.

Applications for Deques

The classic application area for deques is an undo list. Each executed processing step is placed on the deque. When the “undo” function is called, the last edit placed on the deque is taken and undone.

Up to this point, this is a classic LIFO principle, so we could also implement it with a stack.

For memory reasons, however, we should limit the undo history, e.g., to 100 entries. When using a stack, the oldest elements would be at its bottom and could not be removed. With a deque, however, this is not a problem since we can remove elements from both sides.

The following diagram shows an undo history limited to five entries. The numbers count the processing steps; the history was full with steps 1 to 5. To make room for the new step 6, the dequeue operation removes the oldest step, 1, at the tail, and the enqueue operation places step 6 at the head:

The “undo” function takes the most recent step from the head – the same side where the enqueue operation placed it.

The JDK itself uses deques, too: each worker thread of a ForkJoinPool – which parallel streams run on, for example – manages its tasks in a deque of its own. It places new subtasks on one side and, in the default mode, takes them out again on the same side, i.e., according to the LIFO principle.

When a thread runs out of tasks, it takes some from another thread’s deque – from the other side of that deque, according to the FIFO principle. This technique is called work stealing. The thread that owns the deque and the thread that takes tasks from it thus work on different sides.

Time Complexity of the Deque Operations

You can find an introduction to time complexity in the article “Big O Notation and Time Complexity – Easily Explained”.

Deques are usually implemented with arrays or linked lists. With both variants, the cost of each of the six operations is constant, i.e., it does not change with the length of the deque.

Thus, the time complexity of these operations is: O(1).

There is one exception with the array: if it is full and the deque is to grow further, the enqueue operation has to create a new, larger array and copy all elements into it – this one call costs O(n). Since the array grows proportionally to its size each time (to 1.5 to 2 times its size in this series’ ArrayDeque), this rarely happens, and averaged over many calls, the cost remains constant. This is called amortized O(1).

Outlook

In the next part of the tutorial, you will get to know Java’s Deque interface in detail: its methods, the class hierarchy, and which of the JDK implementations to use when. I will show you how to implement a deque yourself using an array later in this series.