The Collections Framework

Queue, Deque & Stack

15 min Lesson 8 of 14

Queue, Deque & Stack

A Queue is a collection designed for holding elements prior to processing. The defining rule is FIFO — First In, First Out: elements are added at one end (the tail) and removed from the other end (the head). Think of a checkout line at a supermarket.

A Deque (double-ended queue, pronounced "deck") generalises the queue: you can add and remove elements at both ends. This single abstraction can act as a queue, a stack, or a sliding-window buffer.

The Queue Interface

java.util.Queue<E> extends Collection and adds two families of methods — one that throws exceptions on failure and one that returns a special value:

Tail (add): add(e) throws IllegalStateException; offer(e) returns false.
Head (remove): remove() throws NoSuchElementException; poll() returns null.
Head (peek): element() throws; peek() returns null.

In practice, prefer the offer / poll / peek trio — they are null-safe and the idiomatic choice for most queues.

Why two method families? The Queue interface was designed to cover bounded queues (like ArrayBlockingQueue) where capacity limits can prevent insertion. The exception-throwing variants signal a programming error; the special-value variants are for flow control where a full or empty queue is a normal condition.

The Deque Interface

java.util.Deque<E> extends Queue and mirrors every method at both ends. The naming convention is clear: methods end in First or Last.

offerFirst(e) / offerLast(e) — add at head / tail.
pollFirst() / pollLast() — remove from head / tail, return null if empty.
peekFirst() / peekLast() — inspect without removing.
push(e) / pop() / peek() — stack aliases that operate on the head.

ArrayDeque — the Go-To Implementation

java.util.ArrayDeque<E> is a resizable circular array that implements Deque. It is the right default choice for both queues and stacks in single-threaded code.

Using ArrayDeque as a Queue (FIFO)

import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> printQueue = new ArrayDeque<>();

printQueue.offer("job-1");
printQueue.offer("job-2");
printQueue.offer("job-3");

// Process in arrival order
while (!printQueue.isEmpty()) {
    String job = printQueue.poll();   // removes head; returns null if empty
    System.out.println("Printing: " + job);
}
// Output:
// Printing: job-1
// Printing: job-2
// Printing: job-3

Declare the variable as Queue<String>, not ArrayDeque<String>. Programming to the interface keeps your code flexible — you can swap in a LinkedList or a bounded ArrayBlockingQueue without changing any other line.

Using ArrayDeque as a Stack (LIFO)

A stack follows LIFO — Last In, First Out. The classic use-cases are undo history, expression parsing, and depth-first traversal.

import java.util.ArrayDeque;
import java.util.Deque;

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

undoStack.push(100);   // pushes to the head
undoStack.push(200);
undoStack.push(300);

System.out.println(undoStack.peek());  // 300 — inspects without removing
System.out.println(undoStack.pop());   // 300 — removes from head
System.out.println(undoStack.pop());   // 200
System.out.println(undoStack.pop());   // 100

Declare the variable as Deque<Integer> when you intend stack semantics. The push / pop / peek aliases on Deque operate exclusively on the head, which is exactly what a stack needs.

Why Avoid java.util.Stack?

Java ships a class called java.util.Stack<E> that has been in the JDK since version 1.0. You should not use it in new code.

Stack extends Vector, which synchronises every method. In single-threaded code that lock acquisition is pure overhead with zero benefit.
Because Stack extends Vector, it inherits get(int index), add(int index, E e), and other indexed-access methods that break the stack abstraction. Callers can insert or remove elements anywhere — that is not a stack.
The Javadoc for Stack itself says: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class."

Never use java.util.Stack in new code. Use Deque<E> stack = new ArrayDeque<>(); instead. It is faster (no synchronisation), exposes only stack-appropriate operations via the Deque interface type, and is the recommendation in the official Javadoc.

Performance Characteristics

ArrayDeque stores elements in a circular array. All four boundary operations — add/remove at head or tail — are amortised O(1). The array doubles when full, which is an occasional O(n) copy, but averaged across all insertions the cost is O(1). There is no per-node allocation overhead as with a linked structure.

LinkedList also implements Deque, but each element is a separate heap object with two pointer fields. For queue and stack workloads, ArrayDeque uses less memory and has better cache locality, making it faster in practice. Prefer ArrayDeque unless you specifically need the List interface on the same object.

Tip — give the deque an initial capacity if you know the size upfront. new ArrayDeque<>(1024) pre-allocates the internal array, avoiding resize copies during the fill phase. The default is 16 elements.

A Practical Example: Balanced Brackets Checker

Checking whether brackets in a string are balanced is a textbook stack problem. Each opening bracket is pushed; each closing bracket must match the top of the stack.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class BracketChecker {

    private static final Map<Character, Character> PAIRS = Map.of(
        ')', '(',
        ']', '[',
        '}', '{'
    );

    public static boolean isBalanced(String input) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char ch : input.toCharArray()) {
            if (PAIRS.containsValue(ch)) {
                stack.push(ch);                 // opening bracket
            } else if (PAIRS.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != PAIRS.get(ch)) {
                    return false;               // unmatched closing bracket
                }
            }
        }
        return stack.isEmpty();                 // any leftover openers = unbalanced
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("({[]})"));   // true
        System.out.println(isBalanced("({[})"));    // false
        System.out.println(isBalanced("((())"));    // false
    }
}

Choosing Between Queue and Deque

Need strict FIFO processing? Declare as Queue<E>, back it with ArrayDeque.
Need a stack (LIFO)? Declare as Deque<E>, back it with ArrayDeque, use push/pop/peek.
Need to manipulate both ends (e.g. a sliding window)? Use Deque<E> with the full First/Last API.
Need thread safety? Look at java.util.concurrent: LinkedBlockingDeque, ConcurrentLinkedQueue, etc.

Summary

Queue defines FIFO semantics; Deque generalises it to both ends and doubles as a stack. ArrayDeque is the correct implementation for both roles in single-threaded code — it is faster and leaner than LinkedList for boundary-only operations. Always declare variables as Queue<E> or Deque<E>, never as the concrete type. And never reach for the legacy Stack class: the Javadoc itself points you to Deque.