Java Deque

Java Deque

java.util.Deque<E> is the interface that makes a single data structure behave as a queue, a stack, and a sliding window buffer simultaneously. "Deque" stands for double-ended queue — every operation that exists for one end also exists symmetrically for the other. You can add to the front or the back, remove from the front or the back, and peek at either end in O(1). The standard implementation ArrayDeque is what the Java documentation explicitly recommends over both LinkedList for queue and Stack for LIFO operations.

What Is Java Deque?

Deque<E> is an interface in java.util that extends Queue<E>. It doubles the Queue contract — where Queue provides tail-in, head-out (FIFO), Deque provides full symmetric access: every operation available at the head is equally available at the tail.

The diagram below shows where Deque fits in the Collections hierarchy and its two primary implementations.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Queue<E>            ← FIFO (tail-in, head-out)
                    └── java.util.Deque<E>    ← double-ended queue (both ends)
                            ├── ArrayDeque    ← resizable circular array (RECOMMENDED)
                            └── LinkedList    ← doubly-linked nodes (also implements List)

KEY FACTS:
  Package    : java.util
  Since      : Java 1.6
  Extends    : Queue<E>
  Implemented: ArrayDeque, LinkedList, ArrayBlockingDeque (concurrent)
  Null       : ArrayDeque throws NullPointerException on null — do not insert null
  Duplicates : allowed
  Thread     : NOT thread-safe (use LinkedBlockingDeque for concurrent access)
  Default impl: ArrayDeque — faster than LinkedList, lower memory, no per-element Node

Basic Overview — The Complete Method Set

Deque defines twelve core methods in three operation categories, each with two directions and two failure modes.

DEQUE METHOD MAP — all 12 operations:

  OPERATION    HEAD (front)              TAIL (back)
  ------------ ------------------------- --------------------------
  INSERT       addFirst(e)               addLast(e)
  (throws)     offerFirst(e) → returns   offerLast(e) → returns
  INSERT       false if full             false if full
  (safe)

  REMOVE       removeFirst()             removeLast()
  (throws)     pollFirst()  → null       pollLast()   → null
  REMOVE       if empty                  if empty
  (safe)

  INSPECT      getFirst()                getLast()
  (throws)     peekFirst()  → null       peekLast()   → null
  INSPECT      if empty                  if empty
  (safe)

  STACK ALIASES (map to head operations):
    push(e)   = addFirst(e)
    pop()     = removeFirst()
    peek()    = peekFirst()

  QUEUE ALIASES (map to standard Queue methods):
    add(e)    = addLast(e)
    offer(e)  = offerLast(e)
    remove()  = removeFirst()
    poll()    = pollFirst()
    element() = getFirst()
    peek()    = peekFirst()

PRODUCTION RULE:
  Always use the null/false-returning group: offerFirst, offerLast,
  pollFirst, pollLast, peekFirst, peekLast — for all routine processing.
  The throwing group (addFirst, removeFirst, getFirst etc.) is for cases
  where an empty or full deque represents a programming error.

Deque as Queue, Stack, and Sliding Window

DEQUE USAGE MODES:

  MODE 1 — FIFO QUEUE (standard Queue behaviour):
    offerLast(e)  → add to tail
    pollFirst()   → remove from head
    peekFirst()   → inspect head
    Use case: task queues, BFS, request processing

  MODE 2 — LIFO STACK (replaces java.util.Stack):
    push(e) / addFirst(e)  → push to head
    pop()   / removeFirst()→ pop from head
    peek()  / peekFirst()  → inspect top
    Use case: undo/redo, expression evaluation, DFS

  MODE 3 — DOUBLE-ENDED (unique to Deque):
    Add/remove from EITHER end in O(1)
    Use case: sliding window algorithms, palindrome checking,
              LRU cache eviction, work-stealing schedulers

  ALL THREE modes use ArrayDeque, which implements Deque.
  No need for three different classes.

When to Use Deque

USE ArrayDeque (as Deque) WHEN:
  1. Both LIFO and FIFO operations are needed on the same data
     — sliding window: add new at tail, evict old from head
     — work-stealing: steal from tail, self-consume from head

  2. A stack is needed — ArrayDeque is faster than java.util.Stack
     — Stack is synchronized even for single-threaded use (legacy overhead)
     — ArrayDeque push/pop are O(1) amortised with no synchronisation cost

  3. A FIFO queue is needed — ArrayDeque is faster than LinkedList
     — No per-element Node allocation, cache-friendly contiguous memory

  4. Both-end access is needed in algorithms:
     — Sliding window maximum: monotonic deque
     — Palindrome check: add all to deque, compare front and back

USE LinkedList (as Deque) ONLY WHEN:
  - Both Deque AND List interfaces (get(index), set(index, e)) are needed
    on the same object in the same method

USE LinkedBlockingDeque WHEN:
  - Multiple threads produce and consume from a shared deque
  - LinkedBlockingDeque.takeFirst() / takeLast() block when empty

DO NOT USE java.util.Stack:
  - Stack extends Vector, which is synchronised — always
  - Every push() and pop() acquires a lock, even in single-threaded code
  - Use ArrayDeque as Deque instead — it is the explicit recommendation
    in the Java documentation since Java 6

How ArrayDeque Works Internally

ArrayDeque uses a resizable array with a circular structure. Two integer indices — head and tail — track the front and back of the logical sequence. The array wraps around using bitwise AND masking, which is faster than modulo division.

ARRAYDEQUE CIRCULAR ARRAY (capacity 8, holding 4 elements):

  elements: [ null | null | "C" | "D" | "E" | "F" | null | null ]
               0      1     2     3     4     5      6      7

  head = 2   (index of front element — next pollFirst() target)
  tail = 6   (index where next offerLast() writes)

  offerLast("G"):
    elements[6] = "G"
    tail = (6 + 1) & 7 = 7

  offerFirst("B"):
    head = (2 - 1) & 7 = 1
    elements[1] = "B"

  pollFirst():
    result = elements[head] = elements[1] = "B"
    elements[1] = null     (help GC — clear the slot)
    head = (1 + 1) & 7 = 2

  WRAP-AROUND (tail reaches array end and loops back to front):
  elements: [ "J" | "K" | null | "D" | "E" | "F" | "G" | "H" | "I" | ]
               0     1     2     3     4     5     6     7
  head = 3,  tail = 2  ← tail is BEFORE head — perfectly valid

  RESIZE (when head == tail AND size > 0 — array is full):
    Double the capacity.
    Copy elements from head → end, then 0 → tail into new[0..size-1].
    head = 0, tail = old size.
    Resize is O(n) amortised — same pattern as ArrayList growth.

WHY ARRAYDEQUE BEATS LINKEDLIST FOR BOTH ENDS:
  - No Node object per element → lower GC pressure
  - Contiguous array → CPU cache prefetching works on sequential access
  - Bitwise mask for wrap-around → no modulo division overhead
  - Both head and tail operations are O(1) amortised

Core Operations with Examples

Head and Tail Operations — The Full Deque API

Output:
=== Adding to head and tail ===
Deque  : [A, B, C, D, E]
Size   : 5

=== Peek at both ends (no removal) ===
peekFirst() : A
peekLast()  : E
Deque unchanged: [A, B, C, D, E]

=== Polling from both ends ===
pollFirst() : A
pollLast()  : E
Deque after : [B, C, D]

=== Safe methods on empty deque ===
pollFirst()  : null
peekFirst()  : null
pollLast()   : null
peekLast()   : null
removeFirst(): throws NoSuchElementException

Deque as a Stack — Replacing java.util.Stack

Output:
=== Deque as stack (LIFO) ===
Stack (top first): [InsertedTable, FormattedBold, PastedImage, TypedText]
peek()  : InsertedTable

Undo sequence:
  Undo: InsertedTable
  Undo: FormattedBold
  Undo: PastedImage
  Undo: TypedText

=== Bracket validation ===
  (a + b) * [c - d]      → balanced
  {x + (y * z}           → NOT balanced
  ((()))                 → balanced
  [{()}]                 → balanced
  ({[}])                 → NOT balanced

Sliding Window Maximum — The Classic Deque Algorithm

The sliding window maximum is one of the most tested Deque patterns in product company interviews. A Deque maintains a monotonically decreasing sequence of indices — the front always holds the index of the current window's maximum.

Output:
=== Sliding window maximum (k=3) ===
Input   : [3, 1, 5, 2, 7, 4, 6, 8, 2, 5]
Maxima  : [5, 5, 7, 7, 7, 8, 8, 8]
Window positions:
  window[0..2] = [3, 1, 5] → max = 5
  window[1..3] = [1, 5, 2] → max = 5
  window[2..4] = [5, 2, 7] → max = 7
  window[3..5] = [2, 7, 4] → max = 7
  window[4..6] = [7, 4, 6] → max = 7
  window[5..7] = [4, 6, 8] → max = 8
  window[6..8] = [6, 8, 2] → max = 8
  window[7..9] = [8, 2, 5] → max = 8

=== Stock peak price per 3-day window ===
Daily prices: [145, 162, 158, 171, 165, 178, 182, 175, 169, 183]
3-day peaks : [162, 171, 171, 178, 182, 182, 182, 183]

Basic Example

Output:
Task queue: [URGENT: Call plumber, Wash dishes, Buy groceries]
Next task : URGENT: Call plumber
Remaining : [Wash dishes, Buy groceries]
Last added: Buy groceries
Remaining : [Wash dishes]

How it works:

1. ›Deque<String> (backed by ArrayDeque) lets you insert and remove at BOTH ends, unlike a plain Queue which only works from one end.
2. ›addLast() puts ordinary tasks at the back, while addFirst() pushes the urgent task straight to the front — both are O(1) operations.
3. ›removeFirst() picks up whatever is currently at the front (the urgent task), and removeLast() separately removes from the back, showing that either end can be read or written independently.
4. ›This double-ended access is exactly what makes Deque usable as a FIFO queue, a LIFO stack, or a sliding window, all with the same class.

Performance Considerations

ArrayDeque vs LinkedList for Deque use: ArrayDeque wins on every axis for pure deque operations. Contiguous array means CPU caches load multiple elements at once during iteration; each LinkedList node traversal jumps to a different heap address and causes a cache miss. No per-element Node allocation means far less GC pressure. The Java documentation explicitly recommends ArrayDeque as the preferred implementation for both Deque and Stack use.

Stack (legacy class) problems: java.util.Stack extends Vector, which synchronises every method with a mutex — even in single-threaded programs. push(), pop(), peek(), and search() all acquire a lock on every call. For single-threaded code, this is pure overhead. ArrayDeque has none of it. The only method Stack has that Deque does not is search(element), which returns the 1-based position from the top — but this is O(n) and rarely useful.

Thread safety: ArrayDeque is not thread-safe. For concurrent both-ends access, use LinkedBlockingDeque from java.util.concurrent, which provides blocking takeFirst() and takeLast() that wait when the deque is empty.

Best Practices

Declare the variable as Deque<E> rather than ArrayDeque<E>. Deque<String> history = new ArrayDeque<>() lets you swap the implementation to LinkedBlockingDeque for thread safety by changing one line. ArrayDeque<String> history = new ArrayDeque<>() exposes implementation details and couples callers to the concrete class. The exception: when you need the descendingIterator() method that Deque exposes — it is already part of the interface, so Deque is sufficient.

Use push()/pop()/peek() when the Deque is used as a stack. These three methods — which all operate on the head — signal to readers that the code is using LIFO semantics. addFirst()/removeFirst()/peekFirst() are equally correct but read like positional operations. Consistent use of the stack-alias methods makes the intent clear without a comment.

Use offerLast()/pollFirst()/peekFirst() when the Deque is used as a queue. This pairing mirrors the Queue interface contract explicitly and makes the FIFO intent visible. add() and poll() work too — they delegate to addLast() and pollFirst() — but the explicit offerLast/pollFirst pair is more readable when both ends are involved in the same method.

Never insert null into an ArrayDeque. ArrayDeque throws NullPointerException on offerFirst(null) and offerLast(null). pollFirst() and pollLast() return null to signal an empty deque — if null elements were allowed, that signal would be lost. If an optional or absent value needs to be enqueued, use Optional<E> as the element type.

Common Mistakes

Mistake 1 — Using java.util.Stack Instead of Deque

Mistake 2 — Iterating in Insertion Order When Reverse Is Needed

Output:
for-each: Page1 Page2 Page3
descending: Page3 Page2 Page1

Mistake 3 — Using LinkedList When ArrayDeque Is Sufficient

Mistake 4 — Calling peek() Without Checking isEmpty() Before Throwing Operations

Interview Questions

Q1. What is Deque in Java and how does it differ from Queue?

Deque<E> is an interface in java.util that extends Queue and models a double-ended queue — every operation available at the head is symmetrically available at the tail. Queue provides tail-in, head-out (FIFO). Deque provides full symmetric access: offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast. A Deque can function as a FIFO queue (use offerLast and pollFirst), a LIFO stack (use push and pop which alias addFirst and removeFirst), or a true double-ended buffer where both ends are used simultaneously. ArrayDeque is the recommended implementation for both use cases.

Q2. Why should ArrayDeque replace java.util.Stack?

java.util.Stack extends Vector, which synchronises every method with a mutex — every push(), pop(), and peek() acquires a lock regardless of whether the code is single-threaded. This is unnecessary overhead. ArrayDeque provides push(), pop(), and peek() with identical stack semantics but no synchronisation — O(1) amortised, no lock acquisition. The Java documentation explicitly recommends ArrayDeque as the preferred stack implementation since Java 6. Stack also has the design flaw of exposing Vector's index-based methods (elementAt(i), insertElementAt(i, e)), which are meaningless for a stack and violate encapsulation.

Q3. How does ArrayDeque implement Deque operations in O(1)?

ArrayDeque uses a resizable circular array with two integer indices: head (front element) and tail (next insertion slot for the back). Both advance using bitwise AND masking: head = (head + 1) & (capacity - 1). offerLast() writes at elements[tail] and advances tail forward; offerFirst() decrements head and writes at elements[head]. Both are array slot operations — O(1). When head == tail (array full), the array doubles in size and elements are copied in O(n). The amortised cost of O(1) comes from the same argument as ArrayList: doubling means the O(n) copy is paid off across n insertions.

Q4. What is the sliding window maximum problem and how does Deque solve it?

Given an array of n numbers and a window of size k, find the maximum in every consecutive window. A naive approach is O(n*k). The Deque solution is O(n): maintain a deque of array indices in decreasing order of their values. For each new element, remove indices from the back whose values are smaller — they can never be the maximum of any remaining window. Remove indices from the front that fall outside the current window. The front always holds the index of the current window's maximum. This monotone deque pattern is a standard product-company interview question at Flipkart, Paytm, and Swiggy.

Q5. What is the difference between offerFirst() and addFirst() in Deque?

Both insert an element at the head. addFirst() throws IllegalStateException if the deque has a capacity limit and is full. offerFirst() returns false instead. For unbounded deques like ArrayDeque, the capacity is never reached — both behave identically. For capacity-bounded implementations like LinkedBlockingDeque, the distinction matters. In production code, offerFirst()/offerLast() are the standard choices because they express "attempt to insert" semantics without needing exception handling for a normal operating condition.

Q6. How does Deque's descendingIterator() differ from regular iteration?

For-each iteration on a Deque traverses elements from head (front) to tail (back) — oldest-added to newest-added. descendingIterator() traverses from tail to head — newest-added first. For ArrayDeque, this is traversal in reverse index order. For LinkedList, it follows node.prev pointers. Neither removes elements. descendingIterator() is the correct pattern for "show most recent items first" use cases like browser history, undo stacks, and recent-activity feeds.

FAQs

What is the difference between Deque and ArrayDeque in Java?

Deque<E> is an interface that defines the contract — all the method signatures for both-ends access. ArrayDeque<E> is a concrete class that implements Deque using a circular resizable array. You should declare variables as Deque<E> (the interface) and instantiate with new ArrayDeque<>() (the implementation). This follows the same pattern as List<E> with new ArrayList<>().

Can ArrayDeque contain null elements?

No. ArrayDeque throws NullPointerException on any attempt to insert null via offerFirst(null), offerLast(null), push(null), or addFirst(null). This is by design: pollFirst() and pollLast() return null to signal an empty deque. If null elements were allowed, that signal would be ambiguous. LinkedList, the other Deque implementation, does allow null elements.

What is a monotone deque and when is it used?

A monotone deque maintains elements in either strictly increasing or strictly decreasing order. Elements that violate the monotone property are evicted from the appropriate end before the new element is inserted. This pattern solves sliding window maximum/minimum queries in O(n) and is also used in optimising certain dynamic programming recurrences. The key insight is that evicted elements can never be the answer for any future query, so removing them early costs nothing.

Is Deque thread-safe in Java?

ArrayDeque and LinkedList are not thread-safe. For concurrent access to a double-ended queue, use LinkedBlockingDeque from java.util.concurrent, which provides blocking putFirst(), putLast(), takeFirst(), takeLast() operations. Producers block on put when the deque is full (if bounded), and consumers block on take when it is empty.

What is the difference between Deque.push() and Deque.addFirst()?

They are identical — push(e) is defined as addFirst(e) in the Deque contract. The distinction is semantic: push() signals that the deque is being used as a stack. addFirst() signals a positional insert. When writing stack-oriented code, push(), pop(), and peek() communicate intent to readers clearly. When writing both-ends code where positional insert is the concept, addFirst() and addLast() are clearer.

How is Deque used in DFS (depth-first search)?

DFS uses a stack — explore as deep as possible before backtracking. Replacing the call stack with an explicit Deque as a stack avoids StackOverflowError for very deep graphs. Push the start node; while the deque is not empty, pop the top node, process it, and push all its unvisited neighbours. Since pop() = removeFirst(), the most-recently-discovered node is always processed next, giving depth-first traversal. Compare to BFS, which uses offerLast/pollFirst (FIFO) for level-by-level traversal.

Summary

Deque<E> is Java's double-ended queue interface — symmetric O(1) access at both the head and tail. The twelve methods form three groups (insert, remove, inspect), each with a throwing variant and a null-returning variant, for each end. The practical recommendation: always prefer the null-returning group (offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast) for routine processing.

ArrayDeque implements Deque with a circular resizable array — faster than LinkedList for all deque operations, and faster than java.util.Stack for stack operations. The Java documentation explicitly recommends it for both use cases.

The three patterns that matter most for interviews: using Deque as a stack replacement for java.util.Stack, the sliding window maximum with a monotone deque, and the both-ends window buffer (add to tail, evict from head). Knowing when to use each of these — and why ArrayDeque is the right implementation for all three — is what separates a confident collections answer from a generic one.

What to Read Next