skip to content

What is a Deque, and how do its head and tail operations let it act as both a queue and a stack?

level: middleimportance: must knowfreq 65%

answer

  1. Deque = double-ended queue ('deck'), insert/remove/examine at both ends
  2. *First / *Last x throwing/special-value forms
  3. FIFO: offerLast + pollFirst; inherited Queue methods do this
  4. Stack: push=addFirst, pop=removeFirst, peek=head
  5. descendingIterator walks tail->head; prefer ArrayDeque over Stack

basics

~20 s

A Deque (double-ended queue) lets you add and remove from both ends. You can use it FIFO like a queue (add at one end, remove from the other) or LIFO like a stack (add and remove from the same end).

solid answer

~40 s

A Deque (double-ended queue, java.util.Deque) supports insertion, removal, and inspection at both the head (front) and the tail (back). It provides explicit end-specific methods in the same two failure styles as Queue: addFirst/offerFirst, addLast/offerLast, removeFirst/pollFirst, removeLast/pollLast, getFirst/peekFirst, getLast/peekLast. Because you control both ends, one structure covers two classic abstractions. As a FIFO queue you add at one end and remove at the other (addLast/pollFirst), which is exactly what the inherited Queue methods (offer/poll/peek) do. As a LIFO stack you push and pop at the same end via push/pop (which delegate to addFirst/removeFirst) or by using the *First methods directly. Deque also adds stack-style convenience methods push and pop, plus descendingIterator to walk tail-to-head. The recommended stack implementation in modern Java is ArrayDeque rather than the legacy Stack class.

code

java · 10 lines
java
Deque<Integer> d = new ArrayDeque<>();

// As a FIFO queue
d.offer(1); d.offer(2);      // offerLast
System.out.println(d.poll()); // 1  (pollFirst -> head)

// As a LIFO stack
d.push(10); d.push(20);      // addFirst
System.out.println(d.pop()); // 20 (removeFirst -> head)
System.out.println(d.peek());// 10 (head = top of stack)

go deeper

for a junior

Knows a deque allows adding/removing at both ends and can be used as either a queue or a stack.

for a middle

Can list the *First/*Last method pairs, map push/pop to addFirst/removeFirst, and explain FIFO vs LIFO usage of the same structure.

for a senior

Explains how inherited Queue methods map to the head/tail, uses descendingIterator, and justifies choosing Deque/ArrayDeque over Stack and LinkedList.

for a principal

Reasons about API design (single type covering two ADTs), null-handling invariants, and when a deque's two-ended access enables algorithms (sliding-window max, work-stealing) that a plain queue cannot.

## What a Deque is **Deque** stands for **double-ended queue** (pronounced 'deck'). It is the `java.util.Deque<E>` interface, which extends `Queue<E>`. Where a plain queue lets you insert at one logical end and remove from the other, a deque lets you insert, remove, and examine at **both** ends — the **head** (front) and the **tail** (back). ## The two failure styles, doubled Just like `Queue`, every deque operation comes in an **exception-throwing** form and a **special-value** form. But each is also split by *which end* it touches, giving a 2x2x3 grid (end x failure-style x action): | Action | First (head), throws | First, special value | Last (tail), throws | Last, special value | |---|---|---|---|---| | Insert | `addFirst(e)` | `offerFirst(e)` | `addLast(e)` | `offerLast(e)` | | Remove | `removeFirst()` | `pollFirst()` | `removeLast()` | `pollLast()` | | Examine | `getFirst()` | `peekFirst()` | `getLast()` | `peekLast()` | The throwing forms throw `NoSuchElementException` on an empty deque (and `IllegalStateException` if a bounded deque is full on insert); the special-value forms return `null` (or `false` for `offer*`). ## How the inherited Queue methods map `Deque` extends `Queue`, so it inherits `add/offer/remove/poll/element/peek`. For a deque these are defined to operate as a **FIFO queue**: the head is where elements leave, the tail is where they enter. - `offer(e)` == `offerLast(e)` (enter at tail) - `poll()` == `pollFirst()` (leave from head) - `peek()` == `peekFirst()` (look at head) So using only the inherited methods gives you a normal first-in-first-out queue. ## Using a Deque as a stack (LIFO) A **stack** is last-in-first-out: the most recently pushed element is the next popped. A deque models this by pushing and popping at the **same** end (the head). Deque adds two convenience methods for exactly this: - `push(e)` == `addFirst(e)` (throws if a bounded deque is full) - `pop()` == `removeFirst()` (throws `NoSuchElementException` if empty) - `peek()` (inherited) looks at the head, i.e. the top of the stack. So `push`/`pop`/`peek` give you a clean stack API backed by a deque. ## descendingIterator A deque's normal iterator goes head-to-tail. `descendingIterator()` returns one that walks **tail-to-head**, useful when you stored things in one order but want to traverse the reverse. ## Why one type, two abstractions Because you can control both ends, a single `Deque` cleanly expresses: - **FIFO queue**: insert at tail, remove at head. - **LIFO stack**: insert and remove at the same end. This is why modern Java guidance is to use a `Deque` (concretely `ArrayDeque`) instead of the old `java.util.Stack` class for stack behavior, and instead of `LinkedList` for most queue/deque needs. ## A note on nulls Like most queues, `ArrayDeque` forbids `null` elements (they would collide with the `null`-means-empty signal of `pollFirst`/`peekFirst`), throwing `NullPointerException` on insertion of `null`.

  • If you push three items A, B, C onto an ArrayDeque-as-stack and then pop, what comes out first and why?
    C. push delegates to addFirst, so C ends up at the head; pop delegates to removeFirst, returning the most recently pushed element — LIFO order.
  • How do the inherited Queue methods (offer/poll/peek) behave on a Deque?
    They operate FIFO: offer adds at the tail (offerLast), poll removes from the head (pollFirst), peek inspects the head (peekFirst).

saying these in an interview costs you the question

  • Saying push/pop operate at opposite ends (both operate at the head/first end)
  • Claiming Deque's inherited poll() removes from the tail (it removes from the head)
  • Confusing getFirst (throws) with peekFirst (returns null)
  • Thinking Deque can only be a queue OR a stack, not both

context

resolving links…