Java Queue and Deque

A queue is a collection that orders elements first-in-first-out (FIFO), like a checkout line: the first item added is the first one removed. A deque (short for "double-ended queue", pronounced "deck") is a more powerful cousin that lets you add and remove elements from both ends, so it can act as a queue, a stack, or a sliding window buffer. Both are core parts of the java.util Collections Framework and show up constantly in real code: task schedulers, undo histories, breadth-first search, and buffering.

Overview / How It Works

In Java, Queue<E> and Deque<E> are interfaces, not concrete classes — you always instantiate an implementing class and program against the interface type. Queue extends Collection and adds FIFO-oriented methods (insert at the tail, remove/inspect the head). Deque extends Queue and adds explicit "First" and "Last" variants of every operation, so you can treat it as a queue (FIFO), a stack (LIFO), or both at once.

The two implementations you will use almost all the time are:

• LinkedList — a doubly linked list. Every element is wrapped in a node holding references to the previous and next nodes. Insertion/removal at either end is O(1), but each node costs extra memory (two references plus object header) and traversal is cache-unfriendly because nodes are scattered across the heap.
• ArrayDeque — a resizable circular array (a ring buffer). Internally it keeps a backing Object[] array plus head and tail indices that wrap around the array bounds. Adding to either end just writes into the next free slot and moves the index; when the array fills up, it is reallocated to double the size and the elements are copied in order. Because the data is contiguous in memory, ArrayDeque is faster and more memory-efficient than LinkedList for almost every use case, and the JDK documentation explicitly recommends it over LinkedList for stack and queue behavior.

There is also PriorityQueue, which implements Queue but is NOT a FIFO structure — it orders elements by natural ordering or a Comparator using a binary heap. It’s worth knowing it exists, but this lesson focuses on the FIFO/deque behavior of LinkedList and ArrayDeque.

Syntax

Queue<String> queue = new LinkedList<>();   // or new ArrayDeque<>()
Deque<String>  deque = new ArrayDeque<>();    // or new LinkedList<>()

queue.offer("item");   // insert at the tail (returns false instead of throwing if it fails)
queue.poll();           // remove & return the head, or null if empty
queue.peek();           // look at the head without removing it, or null if empty

Every Queue method comes in two flavors: one that throws an exception on failure, and one that returns a sentinel value (false or null). Prefer the sentinel-returning versions unless a failure is truly exceptional in your program.

Operation	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove head	remove()	poll()
Inspect head	element()	peek()

Deque mirrors this table but for both ends explicitly:

Operation	First (head)	Last (tail)
Insert	addFirst(e) / offerFirst(e)	addLast(e) / offerLast(e)
Remove	removeFirst() / pollFirst()	removeLast() / pollLast()
Inspect	getFirst() / peekFirst()	getLast() / peekLast()

A Deque can also act as a stack using push(e) (alias for addFirst), pop() (alias for removeFirst), and peek() (alias for peekFirst).

Examples

Example 1: A Simple FIFO Task Queue

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> printQueue = new LinkedList<>();
        printQueue.offer("Report.pdf");
        printQueue.offer("Invoice.docx");
        printQueue.offer("Photo.png");

        System.out.println("Queue: " + printQueue);
        System.out.println("Next to print (peek): " + printQueue.peek());

        while (!printQueue.isEmpty()) {
            String job = printQueue.poll();
            System.out.println("Printing: " + job);
        }

        System.out.println("Queue empty? " + printQueue.isEmpty());
    }
}

Output:

Queue: [Report.pdf, Invoice.docx, Photo.png]
Next to print (peek): Report.pdf
Printing: Report.pdf
Printing: Invoice.docx
Printing: Photo.png
Queue empty? true

Each offer appends to the tail. peek shows the head (the oldest item) without removing it. The loop repeatedly polls the head until the queue is empty, printing jobs in the exact order they were added — that’s FIFO behavior in action.

Example 2: Deque as a Stack (Undo History)

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

public class Main {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Type 'Hello'");
        undoStack.push("Type ' World'");
        undoStack.push("Bold text");

        System.out.println("Undo stack: " + undoStack);

        System.out.println("Undo: " + undoStack.pop());
        System.out.println("Undo: " + undoStack.pop());

        System.out.println("Remaining actions: " + undoStack);
    }
}

Output:

Undo stack: [Bold text, Type ' World', Type 'Hello']
Undo: Bold text
Undo: Type ' World'
Remaining actions: [Type 'Hello']

push inserts at the front, so the most recently pushed action ends up first in the deque. pop removes from the front too, giving classic LIFO (last-in-first-out) behavior — exactly what an undo stack needs. Notice this is the same ArrayDeque object being used as a stack, not a queue.

Example 3: Using Both Ends — Palindrome Check

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

public class Main {
    static boolean isPalindrome(String text) {
        Deque<Character> deque = new ArrayDeque<>();
        for (char c : text.toCharArray()) {
            deque.addLast(c);
        }
        while (deque.size() > 1) {
            if (!deque.pollFirst().equals(deque.pollLast())) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] words = {"level", "hello", "racecar"};
        for (String word : words) {
            System.out.println(word + " -> " + isPalindrome(word));
        }
    }
}

Output:

level -> true
hello -> false
racecar -> true

This is where a deque truly shines: it compares characters from both ends inward, popping from the front with pollFirst and from the back with pollLast in the same loop. A plain Queue couldn’t do this efficiently because it only exposes one end for removal.

Under the Hood

When you call offer on an ArrayDeque, the JVM writes the new element into the backing array at the tail index, then advances tail by one, wrapping back to index 0 if it runs past the array’s end (that’s the "circular" part). Removing from the head does the same at the head index. If head and tail ever meet because the array is full, ArrayDeque allocates a new array (typically double the capacity), copies all elements into it in logical order starting at index 0, and resets the indices — an O(n) operation that happens rarely (amortized O(1) per insertion, just like ArrayList growth).

A LinkedList, by contrast, allocates a new Node object for every element, containing the value and two references (prev and next). Adding or removing at either end simply rewires a couple of references — no resizing or copying — but each element now costs noticeably more memory, and because nodes live at scattered heap addresses, iterating a LinkedList is slower in practice than iterating the contiguous array inside an ArrayDeque, even though both are "O(1) per operation" in Big-O terms.

Common Mistakes

Mistake 1: Using the exception-throwing methods on a possibly-empty queue

remove() and element() throw NoSuchElementException when the queue is empty, which surprises people coming from other languages. Prefer poll() and peek(), which return null instead of throwing.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        try {
            int value = queue.remove();
            System.out.println("Got: " + value);
        } catch (java.util.NoSuchElementException e) {
            System.out.println("Oops: remove() threw NoSuchElementException on an empty queue!");
        }

        Integer safeValue = queue.poll();
        System.out.println("poll() returned: " + safeValue);
    }
}

Output:

Oops: remove() threw NoSuchElementException on an empty queue!
poll() returned: null

Mistake 2: Storing null elements in an ArrayDeque

LinkedList permits null elements, but ArrayDeque explicitly forbids them — it uses null internally as a sentinel to mean "empty slot", so allowing real null values would make poll() ambiguous (is the queue empty, or did it really contain null?). Attempting to add null throws a NullPointerException.

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

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        try {
            deque.add(null);
        } catch (NullPointerException e) {
            System.out.println("ArrayDeque rejects null elements!");
        }

        deque.add("A");
        deque.add("B");
        System.out.println("Deque contents: " + deque);
    }
}

Output:

ArrayDeque rejects null elements!
Deque contents: [A, B]

A third common mistake is treating Queue as if it supports indexed access like a List. The Queue interface deliberately has no get(index) method — if you find yourself wanting random access, you probably want an ArrayList or ArrayDeque used differently, not a Queue.

Best Practices

• Declare variables with the interface type (Queue<E> or Deque<E>), not the concrete class, so you can swap implementations later without changing calling code.
• Prefer ArrayDeque over LinkedList for both queue and stack use cases — it’s faster, more memory-efficient, and the JDK docs recommend it explicitly.
• Use the offer/poll/peek family in normal control flow; reserve add/remove/element for cases where an empty queue truly indicates a bug you want to surface as an exception.
• Never store null in an ArrayDeque — use a sentinel object or Optional if you need to represent "no value".
• Use a Deque instead of the legacy Stack class for LIFO behavior; Stack is synchronized (slower) and extends Vector, which exposes indexed mutation that breaks stack discipline.
• For breadth-first search (BFS) over graphs or trees, use a Queue (usually ArrayDeque) to hold the frontier of nodes to visit next.

Practice Exercises

• Exercise 1: Write a method reverseWithStack(Deque<Integer> input) that uses a second Deque as a stack (via push/pop) to reverse the order of elements in input, printing the reversed list.
• Exercise 2: Simulate a hot-potato / round-robin scheduler: put five player names into a Queue, then repeatedly poll a name, print it, and offer it back to the tail three times each, so each player gets three turns in order.
• Exercise 3: Using a Deque<Integer>, implement a sliding-window maximum for the array {1, 3, -1, -3, 5, 3, 6, 7} with window size 3 (hint: keep indices in the deque, dropping from the back whenever a smaller value is found).

Summary

• Queue models FIFO (first-in-first-out) behavior; Deque extends it to allow insertion and removal at both ends.
• ArrayDeque (circular array) is generally faster and more memory-efficient than LinkedList (doubly linked nodes) for both queue and stack use.
• Each core operation has a throwing form (add, remove, element) and a sentinel-returning form (offer, poll, peek) — prefer the sentinel form for normal control flow.
• A Deque can act as a stack via push/pop, replacing the legacy, synchronized Stack class.
• ArrayDeque does not allow null elements; LinkedList does.
• Deques are the natural tool whenever you need to work from both ends of a sequence, such as palindrome checks or sliding-window algorithms.