Queue & Deque

Interfaces modeling ordered processing of elements — Queue for typically FIFO access, Deque for efficient access at both ends, with ArrayDeque as the modern general-purpose implementation.

Queue and Deque are Collection subinterfaces built around the order in which elements are meant to be processed, rather than around indexed access (like List) or uniqueness (like Set). Queue typically models first-in-first-out processing; Deque ('double-ended queue') generalizes this to efficient insertion and removal at both ends, letting it also serve as a stack.

What Is Queue

java.util.Queue<E> extends Collection<E> and adds methods oriented around processing elements in a defined order — conventionally first-in-first-out (FIFO), though PriorityQueue is a notable exception that orders by priority rather than insertion time. Queue defines two forms of most operations: one that throws an exception on failure, and one that returns a special value (null or false) instead.

Throws exception    Returns special value
Insert       add(e)               offer(e)     -> false if full/rejected
Remove       remove()             poll()       -> null if empty
Examine      element()            peek()       -> null if empty

What Is Deque

java.util.Deque<E> extends Queue<E> and adds explicit first/last variants of every operation, letting a single Deque implementation serve equally well as a FIFO queue, a LIFO stack, or a double-ended buffer.

Throws exception          Returns special value
Insert first addFirst(e)               offerFirst(e)
Insert last  addLast(e)                offerLast(e)
Remove first removeFirst()             pollFirst()
Remove last  removeLast()              pollLast()
Examine first getFirst()               peekFirst()
Examine last  getLast()                peekLast()

ArrayDeque

ArrayDeque is a resizable-array-backed implementation of Deque with no fixed capacity limit and no synchronization overhead. For most stack and queue use cases it's the recommended modern choice — the JDK documentation notes it is generally faster than Stack (a legacy synchronized class) when used as a stack, and faster than LinkedList when used as a queue, due to better memory locality and lower per-element overhead.

import java.util.*;

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(0);
System.out.println(deque);        // [0, 1, 2]
System.out.println(deque.pollFirst()); // 0
System.out.println(deque.pollLast());  // 2
System.out.println(deque);        // [1]

FIFO and LIFO Operations

Using Deque's addLast/pollFirst pair gives FIFO (queue) behavior; using addFirst/pollFirst (or addLast/pollLast) gives LIFO (stack) behavior. Deque also directly provides push() and pop(), defined as aliases for addFirst() and removeFirst(), specifically to support stack-style usage idiomatically.

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack.pop()); // c — LIFO
System.out.println(stack.pop()); // b

Queue<String> queue = new ArrayDeque<>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
System.out.println(queue.poll()); // a — FIFO
System.out.println(queue.poll()); // b

PriorityQueue: Conceptual Overview

PriorityQueue is a Queue implementation backed by a binary heap. It does not process elements in insertion order; instead, poll() always returns the smallest element according to natural ordering (Comparable) or a supplied Comparator. It's useful whenever you need to repeatedly retrieve the 'next most important' item — task scheduling, Dijkstra's algorithm, merge-k-sorted-lists — rather than strict arrival order.

PriorityQueue's iteration order (via iterator()) is not sorted at all — it reflects the internal heap array layout. Only repeated poll() calls return elements in sorted order.

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1 — smallest first, not insertion order
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 5

Null Restrictions

Most Queue implementations, including ArrayDeque and PriorityQueue, prohibit null elements — attempting to add one throws NullPointerException. This is a deliberate design choice: poll() and peek() use a null return value to signal 'the queue is empty,' so allowing null elements would make that signal ambiguous. LinkedList, which also implements Deque, is a notable exception and does permit null elements since it doesn't use null as an empty-queue sentinel in quite the same way — but relying on that is discouraged for portability across Deque implementations.

Deque<String> d = new ArrayDeque<>();
try {
    d.addFirst(null);
} catch (NullPointerException e) {
    System.out.println("ArrayDeque rejects null elements");
}

Basic Syntax and Common Operations

Queue<String> q = new ArrayDeque<>();
q.offer("first");
q.offer("second");
System.out.println(q.peek());   // "first" — look without removing
System.out.println(q.poll());    // "first" — remove and return
System.out.println(q.poll());    // "second"
System.out.println(q.poll());    // null — empty, no exception thrown

Practical Usage

Queue/Deque implementations are the natural building block for breadth-first search (Queue), depth-first search / undo stacks / expression evaluation (Deque as a stack), sliding-window algorithms (Deque as a double-ended buffer), and task scheduling by priority (PriorityQueue).

import java.util.*;

// Breadth-first traversal skeleton using a Queue
void bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> frontier = new ArrayDeque<>();
    Set<Integer> visited = new HashSet<>();
    frontier.offer(start);
    visited.add(start);

    while (!frontier.isEmpty()) {
        int node = frontier.poll();
        System.out.println("Visiting " + node);
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (visited.add(neighbor)) { // true if newly added
                frontier.offer(neighbor);
            }
        }
    }
}

Edge Cases

remove() and element() throw NoSuchElementException on an empty Queue, while poll() and peek() return null instead — mixing up which pair you're using is a common source of unexpected exceptions or unexpected nulls; pick the exception-throwing or null-returning form deliberately based on whether 'empty' is an expected, routine case.

java.util.Stack, from before the Collections Framework, is a legacy synchronized class extending Vector; ArrayDeque used via push()/pop() is the modern, non-legacy replacement and is not synchronized (so it's not automatically thread-safe, but also not paying needless locking overhead in single-threaded use).

PriorityQueue's ordering guarantee applies only to poll()/peek(), not to toString() or iteration, which can surprise developers expecting a fully sorted printout.

Complete Example

import java.util.*;

public class UndoStack {
    private final Deque<String> history = new ArrayDeque<>();

    void perform(String action) {
        history.push(action);
        System.out.println("Did: " + action);
    }

    void undo() {
        String last = history.poll(); // poll(), same as pollFirst() for Deque-as-stack
        if (last == null) {
            System.out.println("Nothing to undo.");
        } else {
            System.out.println("Undid: " + last);
        }
    }

    public static void main(String[] args) {
        UndoStack editor = new UndoStack();
        editor.perform("type 'hello'");
        editor.perform("bold text");
        editor.undo(); // Undid: bold text
        editor.undo(); // Undid: type 'hello'
        editor.undo(); // Nothing to undo.
    }
}

Mental Model

Picture a Queue as a line at a coffee shop: people join at the back and are served from the front — strict first-come-first-served. A Deque is that same line, but with a second door at the front too, so people (or the barista) can also enter or leave from the front — useful both as a normal line (FIFO) and, used only from one end, as a stack of trays (LIFO). A PriorityQueue is not a line at all, but a triage desk: whoever has the highest priority is served next, regardless of arrival order.

Quick Reference

Queue<E>  — typically FIFO; offer/poll/peek (null on empty),
            add/remove/element (throw on empty)
Deque<E>  — Queue + explicit First/Last variants;
            push()==addFirst(), pop()==removeFirst() for stack use

ArrayDeque<E>   — modern general-purpose Queue/Deque/stack, no nulls
LinkedList<E>   — also a Deque, allows null, generally slower in practice
PriorityQueue<E> — heap-based, poll() returns smallest by
                   Comparable/Comparator, not insertion order
Stack<E>        — legacy, synchronized, prefer ArrayDeque instead

Key Takeaways

Queue models ordered processing (typically FIFO); each core operation has an exception-throwing form and a special-value-returning form.

Deque extends Queue with explicit first/last operations, letting one implementation serve as a queue, a stack (via push/pop), or a double-ended buffer.

ArrayDeque is the recommended modern default for both queue and stack use, replacing the legacy Stack and often outperforming LinkedList.

PriorityQueue returns elements from poll() in priority order, not insertion order, and its iteration order is unspecified.

Most Queue/Deque implementations (ArrayDeque, PriorityQueue) reject null elements because null is reserved as the poll()/peek() empty-queue signal.

Queue<String> q = new ArrayDeque<>(); System.out.println(q.element()); // throws NoSuchElementException on empty queue, unexpectedly

Queue<String> q = new ArrayDeque<>(); String head = q.peek(); // returns null instead of throwing if (head == null) { System.out.println("queue is empty"); } element() and remove() throw on an empty queue, while peek() and poll() return null; use the null-returning pair when an empty queue is a routine, expected case rather than an error.

Deque<Integer> d = new ArrayDeque<>(); d.addFirst(null); // throws NullPointerException

Deque<Integer> d = new ArrayDeque<>(); // don't store null; use Optional<Integer> or a sentinel value instead if "no value" is needed

ArrayDeque (like most Queue implementations) forbids null elements because null is reserved to signal an empty queue from poll()/peek().

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3)); System.out.println(pq); // assuming this prints sorted output

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3)); List<Integer> sorted = new ArrayList<>(); while (!pq.isEmpty()) sorted.add(pq.poll()); System.out.println(sorted); // [1, 3, 5] — actually sorted

A PriorityQueue's toString()/iteration reflects its internal heap array, not sorted order; only repeated poll() calls return elements in priority order.

What is the key difference between offer()/poll()/peek() and add()/remove()/element() on a Queue?

offer/poll/peek return a special value (false or null) on failure (e.g. an empty or full queue), while add/remove/element throw an exception (like NoSuchElementException) instead.

How can a Deque be used as a stack, and which methods support this directly?

By always inserting and removing from the same end; Deque provides push() and pop() as direct aliases for addFirst() and removeFirst() specifically for stack-style usage.

Why is ArrayDeque generally recommended over both the legacy Stack class and LinkedList for queue/stack use?

It has no synchronization overhead (unlike the legacy, synchronized Stack) and offers better memory locality and lower per-element overhead than LinkedList's node-based structure, making it faster in typical use.

In what order does PriorityQueue.poll() return elements, and how does that differ from its iteration order?

poll() always returns the smallest remaining element by natural ordering or a supplied Comparator; the iterator (and toString()) instead reflects the internal heap's array layout and is not guaranteed to be sorted.

Why do ArrayDeque and PriorityQueue reject null elements?

Because poll() and peek() use a null return value specifically to signal that the queue is empty; permitting null elements would make that signal ambiguous.

Interview: Why might LinkedList sometimes still be chosen as a Deque implementation despite ArrayDeque generally being faster?

LinkedList permits null elements (unlike ArrayDeque), and it also directly implements List, so it can be useful when both indexed-list-like access to some elements and double-ended operations are genuinely needed together on the same object, though this is an uncommon combination in practice.

Write a method that checks whether a string of parentheses is balanced, using a Deque as a stack.

static boolean isBalanced(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') { stack.push(c); } else if (c == ')') { if (stack.isEmpty()) return false; stack.pop(); } } return stack.isEmpty(); }

Each '(' is pushed; each ')' pops one, failing if the stack is already empty (an unmatched close); balanced means the stack is empty at the end.

What does the third poll() call return, and why doesn't it throw?

It returns null because the queue is now empty; poll() is the special-value-returning form and does not throw NoSuchElementException the way remove() would.

Write a program using a PriorityQueue<Integer> to find the 3 smallest numbers in an int array of arbitrary size, printing them in ascending order.

import java.util.*; public class SmallestThree { public static void main(String[] args) { int[] data = {9, 4, 7, 1, 8, 2, 6}; PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int n : data) { pq.offer(n); } for (int i = 0; i < 3 && !pq.isEmpty(); i++) { System.out.println(pq.poll()); } } }

Offering all elements into the min-heap-backed PriorityQueue and then polling three times returns 1, 2, 4 — the three smallest values in ascending order.

Queue<Integer> q = new ArrayDeque<>();
q.offer(1);
q.offer(2);
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());