Deque Interface

#Introduction

Deque is one of the most useful interfaces in the Collections Framework because it can act as both a Queue and a Stack.

The name comes from Double Ended Queue. It allows insertion and removal from both ends.

#What is Deque?

Package:

java.util.Deque

#Core Idea

A normal Queue: insert at rear, remove from front.

A Deque: insert/remove from either end.

Therefore Deque = Queue behaviour + Stack behaviour.

#Deque as a Queue

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

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

deque.pollFirst();   // returns 10

• offerLast() → insertion at rear
• pollFirst() → removal from front

This gives normal FIFO behaviour.

#Deque as a Stack

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

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

#Why Deque is Better Than Stack

// Legacy
Stack<Integer> stack = new Stack<>();

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

Why prefer Deque?

• Stack inherits from legacy Vector
• Vector synchronizes operations
• ArrayDeque avoids unnecessary synchronization overhead
• Deque provides a cleaner abstraction for stack operations

#Deque Method Families

This is the most important part to memorize.

Just like Queue:

• add… → exception on failure; offer… → special-value (false) failure
• remove… → exception if empty; poll… → null if empty
• get… → exception if empty; peek… → null if empty

Easy Mental Model

#ArrayDeque

ArrayDeque is the most important Deque implementation.

Package:

java.util.ArrayDeque

Declaration:

public class ArrayDeque<E>
        extends AbstractCollection<E>
        implements Deque<E>,
                   Cloneable,
                   Serializable

It is:

• Resizable
• Array-backed
• Not synchronized
• Does not permit null
• Efficient at both ends

Internal Structure

Unlike LinkedList, ArrayDeque does not create a Node object for every element. It uses an internal array and maintains positions indicating where elements should be inserted/removed.

Why ArrayDeque Is Efficient

Adding/removing from either end generally requires only adjusting internal positions. There is no need to shift all elements, as would happen when inserting/removing at the beginning of an ArrayList.

Circular Buffer Concept

A useful mental model for ArrayDeque is a circular array. Suppose the array reaches its end — [A][B][C][D][ ][ ]. The next insertion doesn't necessarily need to move everything; the logical positions can wrap around: [ ][ ][C][D][A][B].

The implementation uses modular/wraparound indexing to treat the array as circular. When the array becomes full, it grows.

Why a Circular Structure?

Without circular indexing, repeatedly removing from the front could create unused space:

This keeps end operations efficient.

ArrayDeque Growth

ArrayDeque is dynamically resizable. When there is insufficient space:

Occasional resizing costs O(n), while ordinary insertion remains amortized O(1).

Why Doesn't ArrayDeque Allow null?

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

deque.offer(null);

NullPointerException

Why? Because Deque methods such as peek() and poll() use null to represent "no element available". Allowing null would make the result ambiguous.

#ArrayDeque vs LinkedList

Both implement Deque, but their internal structures differ: ArrayDeque → resizable array; LinkedList → doubly linked nodes.

For a pure Queue/Deque workload, prefer ArrayDeque unless you have a specific reason to use LinkedList.

#Deque vs Stack

#Stack and Queue Operations Using Deque

Stack (LIFO)

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

Queue (FIFO)

Use offerLast(), pollFirst() and peekFirst():

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

queue.offerLast(10);
queue.offerLast(20);
queue.offerLast(30);

System.out.println(queue.pollFirst());

10

Deque as Both

#More Deque Operations

descendingIterator()

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

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

Iterator<Integer> it = deque.descendingIterator();

30
20
10

Useful when you need reverse traversal.

removeFirstOccurrence() and removeLastOccurrence()

deque.removeFirstOccurrence(20);   // removes the first matching occurrence
deque.removeLastOccurrence(20);    // removes the last matching occurrence

These operations require searching and are therefore generally O(n).

Deque Does Not Provide Random Access

You cannot do deque.get(3); like an ArrayList. Deque is designed around the front + rear, not arbitrary indexes.

#Time Complexity

For ArrayDeque:

#Real-World Use Cases

Stack

• Expression evaluation — infix → postfix
• Balanced parentheses — ( [ { } ] )
• Undo operations — Action 1, Action 2, Action 3 pushed onto a stack

Queue

Task processing: Request → Deque → Worker.

Sliding Window Algorithms

Deque is extremely useful for problems such as "find the maximum value in every window of size K". A monotonic deque can solve this efficiently — a common coding-interview application.

Palindrome Checking

Compare front ↔ rear using pollFirst() and pollLast().

#Decision Framework

Final Mental Model