Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Java

Double-Ended Queues

Explore the concept of double-ended queues or deques, which allow element insertion and removal from both front and rear ends. Understand their implementation using Java's ArrayDeque class, common operations, time complexity, and practical applications like sliding window problems and undo/redo mechanisms.

We'll cover the following...

A deque stands for a double-ended queue. It is a more flexible version of a queue that allows insertion and deletion from both the front and the rear.

In a normal queue, insertion happens only at the rear and deletion happens only at the front. In a deque, both ends are fully active.

Visualization of a deque
Visualization of a deque

This makes the deque a generalization that can behave like a queue, a stack, or something in between, depending on how it is used.

A deque is useful when a problem needs controlled access to both ends of the structure. It appears in sliding window problems, palindrome checking, scheduling, and caching systems.

Example

To understand how a deque works, consider the following example. If a deque currently contains:

A deque with 3 elements
A deque with 3 elements

After inserting 88 at the front, the deque becomes:

Inserting an element at the front of a deque
Inserting an element at the front of a deque

After inserting 91 at the rear, the deque becomes:

Inserting an element at the rear of a deque
Inserting an element at the rear of a deque

After removing 88 from the front, the deque becomes:

Removing an element from the front of a deque
Removing an element from the front of a deque

After removing 91 from the rear, the deque becomes:

Removing an element from the rear of a deque
Removing an element from the rear of a deque

This two-sided behavior is what makes the deque more versatile than a regular queue.

Python implementation

Java's standard library provides a built-in Deque interface through the java.util package, implemented by ArrayDeque. There is no need to build one from scratch. Here's how to use it:

Java 25
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
    public static void main(String[] args) {
        // Create an empty deque
        Deque<Integer> dq = new ArrayDeque<>();
        // Insert at rear
        dq.addLast(10);
        dq.addLast(20);
        dq.addLast(30);
        // Insert at front
        dq.addFirst(5);
        // Delete from rear
        dq.removeLast();
        // Delete from front
        dq.removeFirst();
        // Peek at front
        int frontElement = dq.peekFirst();
        System.out.println("Front element is: " + frontElement);
        // Peek at rear
        int rearElement = dq.peekLast();
        System.out.println("Rear element is: " + rearElement);
        // Check if empty
        boolean isEmpty = dq.isEmpty();
        System.out.println("Is the queue empty? " + isEmpty);
        // Get size
        int size = dq.size();
        System.out.println("Size: " + size);
    }
}
...