skip to content

Queue, Deque & ArrayDeque

Queue offers two operation families — exception-throwing add/remove/element and value-returning offer/poll/peek — and Deque extends it to both ends. Interviewers expect ArrayDeque as your stack, not the legacy synchronized Stack class.

part ofJavaread it →
on this pageshow

questions

6

What is Java's Queue interface, and how do its two families of insert, remove and inspect operations differ on failure?

level: juniorimportance: must knowfreq 70%

answer

  1. Three actions x two failure styles = six methods
  2. add/remove/element throw; offer/poll/peek return false/null
  3. poll/peek return null on empty; remove/element throw NoSuchElementException
  4. add throws IllegalStateException when bounded queue full; offer returns false
  5. null returns clash with nullable elements -> most queues forbid null

basics

~10 s

Queue is the java.util interface for holding elements before processing, typically FIFO. add/remove/element throw when they cannot act; offer/poll/peek report a full or empty queue by returning false or null.

solid answer

~50 s

java.util.Queue is a Collection for holding elements before processing, typically FIFO. It defines six core operations in two parallel families. The exception-throwing family is add (insert), remove (remove head), and element (look at head); each throws if it can't act: add throws IllegalStateException when a bounded queue is full, while remove and element throw NoSuchElementException on an empty queue. The special-value family is offer (insert), poll (remove head), and peek (look at head); offer returns false when a bounded queue has no room, and poll and peek return null on an empty queue instead of throwing. Choose the special-value methods when emptiness or fullness is a normal, expected condition you want to test for, and the throwing methods when failure is genuinely exceptional. Note that null returns are ambiguous if the queue is allowed to hold null elements, which is one reason most Queue implementations forbid null.

code

java · 13 lines
java
Queue<String> q = new ArrayDeque<>();
q.offer("a");           // true

// special-value family: safe drain
String head;
while ((head = q.poll()) != null) {
    System.out.println(head);
}

// now empty
System.out.println(q.peek());   // null (no throw)
// q.element();                 // would throw NoSuchElementException
// q.remove();                  // would throw NoSuchElementException

go deeper

for a junior

Can name the two families and state that one throws while the other returns false/null.

for a middle

Names the exact exceptions (IllegalStateException for full, NoSuchElementException for empty) and the special return values, and knows the null-forbidding rationale.

for a senior

Articulates the design intent (expected vs exceptional failure), recommends offer for bounded queues, and writes idiomatic poll-based drain loops.

for a principal

Frames the dual API as a deliberate control-flow contract, discusses how it interacts with bounded/concurrent implementations (back-pressure via offer with timeout) and the null-ambiguity invariant across the collection hierarchy.

## What a Queue is A **Queue** is a collection designed to hold elements before they are processed, typically in **FIFO** (first-in, first-out) order: the element that has been waiting longest is the next one removed. Think of a line at a checkout. In Java, `java.util.Queue<E>` is an interface that extends `Collection<E>`. ## The three logical operations Every queue supports three logical actions: - **Insert** an element (add it, usually at the tail). - **Remove** an element (take the head off). - **Examine** an element (look at the head without removing it). ## Why there are two method families For each of those three actions, Java provides **two** methods that behave differently when the operation **cannot** be performed (the queue is empty for remove/examine, or full for insert in a capacity-bounded queue). This gives six methods total: | Action | Throws on failure | Returns special value on failure | |---|---|---| | Insert | `add(e)` | `offer(e)` | | Remove | `remove()` | `poll()` | | Examine | `element()` | `peek()` | ### Exception-throwing family (add / remove / element) - `add(e)`: inserts; returns `true` on success. If a **capacity-restricted** queue is full, it throws **`IllegalStateException`**. (`Queue` redeclares `Collection.add` with this rule.) - `remove()`: removes and returns the head. If the queue is **empty**, throws **`NoSuchElementException`**. - `element()`: returns the head **without** removing it. If empty, throws **`NoSuchElementException`**. Use these when being unable to act is a *bug* — you expect the element to be there, and a crash is the right outcome. ### Special-value family (offer / poll / peek) - `offer(e)`: inserts; returns `true` on success, **`false`** if it can't insert (e.g. a bounded queue is full). It does not throw for the ordinary 'full' case, so it is the right choice for bounded queues. An argument the queue cannot take still throws: `offer(null)` on an `ArrayDeque` is a `NullPointerException`. - `poll()`: removes and returns the head, or returns **`null`** if the queue is empty. - `peek()`: returns the head without removing it, or **`null`** if the queue is empty. Use these when emptiness/fullness is a *normal, expected* state you want to branch on, e.g. a draining loop: `while ((item = queue.poll()) != null) { process(item); }`. ## The null ambiguity Because `poll()` and `peek()` use `null` to mean 'nothing there', storing an actual `null` element would make their results ambiguous. For this reason most implementations (`ArrayDeque`, `PriorityQueue`, the concurrent queues) **forbid null elements** and throw `NullPointerException` if you try to insert one. `LinkedList` is the notable exception: it permits null, and `Queue`'s Javadoc says null should not be inserted even where an implementation permits it. ## How to choose - Bounded/back-pressure-aware producer: prefer `offer` (test the boolean) over `add` (which throws). - Pulling work until exhausted: prefer `poll`/`peek` and check for `null`. - Invariant 'this must not be empty': `remove`/`element` make the failure loud. This dual API is a deliberate design so callers can pick *control flow via return value* or *control flow via exceptions* depending on whether failure is expected or exceptional.

  • Why do most Queue implementations forbid null elements?
    Because poll() and peek() return null to signal an empty queue. If null were a legal element, a null return would be ambiguous (was it an element or emptiness?), so implementations like ArrayDeque and PriorityQueue throw NullPointerException on null insertion.
  • Which method would you use to drain a queue in a loop and why?
    poll(), because it returns null on empty, letting you write while ((x = q.poll()) != null) without catching exceptions for the normal termination case.

  • Saying remove() returns null on empty (it throws NoSuchElementException)
  • Claiming both families throw, or both return null
  • Thinking add() returns false when full (it throws; offer() returns false)
  • Assuming you can safely store null in a Queue and still rely on poll/peek

java.util.Queue
Java 1.5

context

open as a page

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%

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).

open as a page

How does Java's ArrayDeque work inside: its circular array, how head and tail move and wrap, how it grows, and why it refuses null?

level: middleimportance: should knowfreq 34%

basics

~20 s

ArrayDeque is a circular Object array with head and tail indices that wrap at its ends, keeping one slot null between calls. An insert that fills that slot grows the array. Null is refused because a null cell means empty.

open as a page

Why is ArrayDeque recommended over the legacy java.util.Stack class for stack behavior?

level: middleimportance: should knowfreq 60%

basics

~10 s

Stack is old and extends Vector, so every stack operation takes a lock and it exposes index-based methods that break stack semantics. ArrayDeque is likely faster, unsynchronized, and gives a clean push/pop/peek stack API.

open as a page

What is ArrayDeque, how does it store elements, and why is it generally preferred over LinkedList for a FIFO queue?

level: seniorimportance: should knowfreq 45%

basics

~20 s

ArrayDeque is a resizable circular-array Deque. Holding references in one array, it is likely faster and lighter than LinkedList, which wraps every element in a two-pointer node, so it is the better default for a plain queue.

open as a page

Given a concurrency or capacity requirement, how do you choose among Queue/Deque implementations (ArrayDeque, PriorityQueue, the concurrent and blocking variants)?

level: seniorimportance: should knowfreq 40%

basics

~20 s

For a single-threaded queue or stack use ArrayDeque. For priority ordering use PriorityQueue. For multiple threads use a concurrent queue like ConcurrentLinkedQueue, and when you need blocking/capacity limits use a BlockingQueue such as ArrayBlockingQueue or LinkedBlockingQueue.

open as a page