Deque Data Structure

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

• What is a deque?
• What operations does a deque provide?
• What are the applications for deques?
• Which deque interfaces and classes does the JDK provide?
• Which deque implementation should you use for which purposes?
• How to implement a deque yourself in Java?

What Is a Deque?

A deque is a list of elements where elements can be inserted and extracted 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:

• “Enqueue at front”: Adding elements to the head of the deque
• “Enqueue at back”: Adding elements to the tail of the deque
• “Dequeue at front”: Removing elements from the head of the deque
• “Dequeue at back”: Removing elements from the tail of the deque

(As with the queue, the corresponding methods of the Java deque implementations are named differently; more on this in the next part of the tutorial, “Java Deque Interface”).

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.

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. In both cases, the cost of inserting and removing elements on both sides is independent of the length of the deque, i.e., constant.

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