Deque

A normal queue allows us to add elements at the rear and remove elements from the front.

A stack allows us to add and remove elements from the same end.

But what if we want to add or remove elements from both ends?

That's where a Deque comes in.

Deque is short for Double-Ended Queue. It is a linear data structure that allows us to insert and remove elements from both the front and the rear.

How a Deque Works

Imagine a row of people:

Front                         Rear
  ↓                             ↓
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘

With a normal queue, we would typically:

Add → Rear
Remove → Front

But with a deque, we can do both:

Add    → Front or Rear
Remove → Front or Rear

So we can add 5 at the front:

5 → 10 → 20 → 30 → 40

Or add 50 at the rear:

10 → 20 → 30 → 40 → 50

We can also remove from either side.

Main Deque Operations

The most important operations are:

addFirst()    → Add at the front
addLast()     → Add at the rear

removeFirst() → Remove from the front
removeLast()  → Remove from the rear

peekFirst()   → View the front
peekLast()    → View the rear

You can think of a deque like a queue with two doors.

          Add / Remove
                ↓
Front  ←  10 20 30 40  →  Rear
                ↑
          Add / Remove

Both ends are available.

Deque in Java

Java provides the Deque interface.

A commonly used implementation is ArrayDeque.

import java.util.ArrayDeque;
import java.util.Deque;

class Main {
    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();

        deque.addLast(20);
        deque.addLast(30);
        deque.addFirst(10);

        System.out.println(deque);
    }
}

Output:

[10, 20, 30]

Here:

addFirst(10)

added 10 to the front, while:

addLast(20)
addLast(30)

added elements to the rear.

Adding at the Front

Suppose we have:

20 → 30

We can add 10 to the front:

deque.addFirst(10);

Now:

10 → 20 → 30

Adding at the Rear

We can add 40 to the rear:

deque.addLast(40);

Now:

10 → 20 → 30 → 40

Removing from the Front

We can remove the first element:

int value = deque.removeFirst();

System.out.println(value);

Output:

10

The deque becomes:

20 → 30 → 40

Removing from the Rear

We can also remove the last element:

int value = deque.removeLast();

System.out.println(value);

Output:

40

The deque becomes:

20 → 30

This ability to remove from either side is what makes a deque different from a normal queue.

Viewing the Front and Rear

We can look at the first element without removing it:

System.out.println(deque.peekFirst());

And we can look at the last element:

System.out.println(deque.peekLast());

For:

10 → 20 → 30

we get:

peekFirst() → 10
peekLast()  → 30

Neither operation removes anything.

Deque as a Stack

A deque can actually behave like a stack.

Remember that a stack follows:

LIFO
Last In, First Out

We can use only one end of the deque:

deque.push(10);
deque.push(20);
deque.push(30);

Now:

30
20
10

If we call:

deque.pop();

30 is removed first.

So a deque can provide stack-like behavior.

Deque as a Queue

A deque can also behave like a normal queue.

We can add elements at the rear:

deque.addLast(10);
deque.addLast(20);
deque.addLast(30);

and remove them from the front:

deque.removeFirst();

This gives us:

10 → 20 → 30
↑
Removed first

So a deque can act as both a queue and a stack.

Deque vs Queue

The main difference is where elements can be added and removed.

A queue restricts how elements enter and leave.

A deque gives us more flexibility.

Deque vs Stack

A stack usually works with one end:

Top
 ↓
30
20
10

A deque works with both ends:

Front             Rear
 ↓                  ↓
10 → 20 → 30 → 40

We can insert or remove from either side.

Therefore, a deque is more flexible than a traditional stack.

Time Complexity

A well-implemented deque provides constant-time operations at both ends.

This is one of the main reasons deques are useful in DSA.

Real-Life Example

Imagine a line at an airport where people can enter or leave from either end of a controlled section.

Front                    Rear
 ↓                         ↓
John → Jason → Alex → Michael

A person can potentially be added or removed from either side.

That's the basic idea of a double-ended queue.

Another useful example is a train of connected cars where operations can happen from either end.

Deque in Sliding Window Problems

One of the most important DSA applications of a deque is the sliding window technique.

Suppose we have:

[2, 1, 5, 3, 4, 6]

and need to process elements within a moving window.

A deque can help us efficiently maintain useful elements as the window moves.

For example, when finding the maximum value in every window, we can remove elements from the rear that are no longer useful and remove elements from the front when they leave the window.

This can lead to very efficient solutions.

We'll explore this technique later when we study sliding window problems.

Deque and Palindromes

A deque can also be useful for checking whether a string is a palindrome.

Suppose:

"madam"

We can compare characters from both ends:

m → a → d → a → m
↑             ↑
Front         Rear

Compare:

m == m
a == a

Since the characters match, the string is a palindrome.

The ability to access both ends makes a deque suitable for this kind of problem.

A Complete Example

Let's use a deque with strings:

import java.util.ArrayDeque;
import java.util.Deque;

class Main {
    public static void main(String[] args) {

        Deque<String> names = new ArrayDeque<>();

        names.addLast("John");
        names.addLast("Jason");
        names.addLast("Alex");

        names.addFirst("Michael");

        System.out.println(names);

        System.out.println("First: " + names.peekFirst());
        System.out.println("Last: " + names.peekLast());

        names.removeFirst();
        names.removeLast();

        System.out.println(names);
    }
}

Output:

[Michael, John, Jason, Alex]

First: Michael
Last: Alex

[John, Jason]

Here we used both ends of the deque to add and remove elements.

Important Java Note

Although Java has a Stack class, ArrayDeque is generally preferred for stack-like operations in modern Java code.

For example:

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.pop());

Output:

30

The same ArrayDeque class can therefore be used for both stack and queue-style operations.

The Main Idea

A Deque (Double-Ended Queue) is a data structure that allows elements to be inserted and removed from both the front and the rear.

The main operations are:

addFirst()    → Add at front
addLast()     → Add at rear

removeFirst() → Remove from front
removeLast()  → Remove from rear

peekFirst()   → View front
peekLast()    → View rear

Think of it as a structure with two accessible ends:

Front                         Rear
  ↓                             ↓
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
  ↑                             ↑
Add/Remove                  Add/Remove

A deque combines the flexibility of a stack and a queue by allowing insertion and deletion from both ends.