Queues

This post assumes basic Java collections and loops. Review arrays and trees and Big O notation if you need a refresher.

What are Queues?

A queue is a data structure that holds items waiting to be processed. In a conventional queue, items leave in the same order they arrived: first in, first out, or FIFO. You add an item at the rear and remove the next item from the front.

Think of a printer receiving jobs A, B, and C. If nobody changes their order, A is taken first, then B, then C. Adding job D does not move it ahead of the jobs already waiting. The queue preserves that order while the application decides what processing each job means.

This makes a queue useful when the oldest pending item should be handled next. A stack follows a different rule, handling the newest item first. Choosing between them changes the order of work even when both contain exactly the same values.

A queue describes how items are accessed; it does not require a particular storage layout. Arrays and linked nodes can implement the same FIFO behavior. We will explain its characteristics first, then examine those implementations and use a queue in Java to traverse a tree level by level.

What are Queues characteristics?

Arrival Order and Access Operations

The front, also called the head, holds the earliest item still waiting. The rear is where new items arrive. Restricting additions and removals to these ends makes the FIFO rule explicit.

Three operations define this behavior:

Operation	Meaning	Example starting with [A, B], front first
Enqueue C	Append C at the rear	[A, B, C]
Dequeue	Remove and return the front item	Returns A, leaving [B]
Peek	Read the front without removing it	Returns A, leaving [A, B]

Each row starts from the same initial queue. If we enqueue C and then dequeue, the remaining queue is [B, C]. C cannot overtake B.

flowchart LR
    Incoming[New job C] -->|Enqueue at rear| Rear[Rear]
    Rear --> C[C]
    C --> B[B]
    B --> A[A]
    A -->|Dequeue from front| Worker[Worker]

For a single worker, FIFO determines the order in which waiting jobs are taken. With several workers, an earlier job may finish later because it takes longer; a FIFO queue alone does not guarantee completion order.

Storage and Operation Costs

An array seems like an obvious starting point: store A at index 0, B at index 1, and append new items. But removing index 0 and shifting every remaining item left takes O(n) time. Repeatedly draining n items this way takes O(n²) total time.

We can avoid those shifts by moving a position marker instead of moving all the values.

A Circular Array

A circular buffer treats the end of an array as connected to its beginning. Keep a head index for the next item to remove, a tail index for the next insertion, and a size to distinguish empty from full.

For a capacity of 4, the next index is (index + 1) % 4. The remainder operator makes index 3 wrap back to 0.

Action	Slots 0, 1, 2, 3	Head	Tail	Size	Logical queue
Enqueue A, B, C	A, B, C, empty	0	3	3	A, B, C
Dequeue A	empty, B, C, empty	1	3	2	B, C
Enqueue D	empty, B, C, D	1	0	3	B, C, D
Enqueue E	E, B, C, D	1	1	4	B, C, D, E

The physical array now begins with E, but the logical queue begins at head, which still points to B. The separate size tells us that equal head and tail indices mean full in the final row, rather than empty. Other designs reserve an unused slot instead.

A fixed capacity circular queue can enqueue, dequeue, and peek in O(1) time, but it needs a policy when full: reject an insertion, wait, or deliberately overwrite old data. Those policies have different meanings; silently dropping old work is usually wrong for a task queue.

A resizable circular array allocates more space and copies live items when necessary. A growth operation costs O(n), while geometric growth spreads that cost across many insertions, giving amortized O(1) enqueue. Amortized describes the average cost over a sequence, so an individual insertion can still be slower.

Linked Nodes

A linked queue keeps a reference to both its first and last nodes. Enqueue links a new node after the last one; dequeue moves the first reference to the next node. When removing the final node, the implementation must also clear the last reference.

With both references, neither operation needs to traverse the queue. The tradeoff is a separate node allocation and extra references per item, along with less contiguous storage.

Storage strategy	Enqueue	Dequeue at front	Peek	Main tradeoff
Array with shifting	Amortized O(1) if grown geometrically	O(n)	O(1)	Removal repeatedly moves items
Fixed circular array	O(1) when space exists	O(1)	O(1)	Must handle full capacity
Geometrically grown circular array	Amortized O(1), O(n) on growth	O(1)	O(1)	Occasional copy and spare capacity
Linked nodes with front and rear references	O(1)	O(1)	O(1)	Node allocation and pointer overhead

These costs describe the storage operations under the usual model of constant time reference access; they are not latency guarantees for allocation or garbage collection.

Queues in action - code examples

Basic Queue Operations in Java

Java’s Queue<E> is an interface; the implementation supplies the ordering and storage. For a FIFO queue within one thread, we can use ArrayDeque<E>. Although a deque supports both ends, declaring the variable as Queue<String> exposes the queue operations we need.

The API provides paired methods for different failure handling:

Action	Special result	Exception alternative
Insert	offer(e) returns false if capacity prevents insertion	add(e) throws if capacity prevents insertion
Remove head	poll() returns null when empty	remove() throws when empty
Read head	peek() returns null when empty	element() throws when empty

These are the contracts documented by the Java Queue API. Invalid elements can still cause exceptions with offer; its boolean result is not a general exception replacement.

Save this as QueueBasics.java:

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

public class QueueBasics {
    public static void main(String[] args) {
        Queue<String> jobs = new ArrayDeque<>();
        jobs.offer("A");
        jobs.offer("B");
        jobs.offer("C");

        System.out.println(jobs.peek()); // Inspect A without removing it.
        while (!jobs.isEmpty()) {
            System.out.println(jobs.poll());
        }
        System.out.println(jobs.poll()); // Empty queue: null.
    }
}

Output:

A
A
B
C
null

The first A comes from peeking; the second comes from removing it. That repeated value demonstrates the difference between observing and consuming the next item.

ArrayDeque grows as needed, rejects null elements, and is not thread safe. Its normal queue operations have amortized constant cost; searching for an arbitrary value is linear. An initial capacity is a sizing hint, rather than a maximum queue length. These properties are documented in the ArrayDeque API.

Breadth-First Traversal

Suppose we want to visit a tree’s root, then its children, then its grandchildren. This is breadth-first traversal. The queue holds discovered nodes whose children we have not yet examined: the pending frontier.

Consider this tree:

flowchart TB
    A[A] -->|Left child| B[B]
    A -->|Right child| C[C]
    B -->|Left child| D[D]
    B -->|Right child| E[E]
    C -->|Right child| F[F]

Start by enqueuing A. Remove A, visit it, and append B and C. Removing B appends D and E behind C. This placement is the central idea: C was already waiting, so it is visited before B’s children.

Node removed and visited	Queue afterward, front first
None: initialize	A
A	B, C
B	C, D, E
C	D, E, F
D	E, F
E	F
F	Empty

The code needs only three steps inside the loop: remove the next node, record its value, and append its existing children. Node below is a small data holder, and List<String> collects the visit order so we can inspect the result. Save the complete example as BreadthFirstExample.java:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class BreadthFirstExample {
    static class Node {
        final String value;
        Node left;
        Node right;

        Node(String value) {
            this.value = value;
        }
    }

    static List<String> breadthFirst(Node root) {
        List<String> order = new ArrayList<>();
        if (root == null) {
            return order;
        }

        Queue<Node> pending = new ArrayDeque<>();
        pending.offer(root);

        while (!pending.isEmpty()) {
            Node current = pending.poll();
            order.add(current.value);

            // Append children behind nodes already waiting.
            if (current.left != null) {
                pending.offer(current.left);
            }
            if (current.right != null) {
                pending.offer(current.right);
            }
        }
        return order;
    }

    public static void main(String[] args) {
        Node root = new Node("A");
        root.left = new Node("B");
        root.right = new Node("C");
        root.left.left = new Node("D");
        root.left.right = new Node("E");
        root.right.right = new Node("F");

        System.out.println(breadthFirst(root));
        System.out.println(breadthFirst(null));
    }
}

Run it with javac BreadthFirstExample.java followed by java BreadthFirstExample:

[A, B, C, D, E, F]
[]

The null root check handles an empty tree, and the child checks prevent null entries from reaching the queue. Left children are enqueued before right children, which determines the order within each level. Replacing this FIFO behavior with stack behavior would visit a branch before finishing the current level.

For n nodes, each node is enqueued and dequeued once, so traversal takes O(n) time. If w is the largest number of nodes on any level, the queue uses O(w) auxiliary space: it may contain parts of two neighboring levels, but its size stays proportional to the maximum width. The returned list separately uses O(n) space. A wide tree therefore needs a larger queue than a narrow tree with the same number of nodes.

This example assumes a proper tree with no cycles or shared child nodes. For a general graph, track visited vertices and mark them when enqueuing, so multiple edges cannot repeatedly schedule the same vertex. With adjacency lists, breadth-first graph traversal takes O(V + E) time for the reachable vertices and edges.

What problems can Queues solve?

Processing Waiting Work

A queue is useful when work should wait in arrival order: a local event loop, a simulation waiting line, or the frontier of a breadth-first traversal. It is less useful when you need frequent arbitrary lookups or removals by value; those operations lose the benefit of restricting access to the ends.

Choosing a Different Ordering

Do not assume that every Java Queue implementation is FIFO. A PriorityQueue selects the smallest item under its ordering, regardless of arrival time. Equal priorities do not guarantee arrival order. That makes it useful for choosing an urgent task, but substituting it into our traversal would discard the level ordering argument.

Coordinating Producers and Consumers

Concurrency is a separate concern. A BlockingQueue supports thread safe producer and consumer operations, including waiting for work or space. A bounded FIFO implementation such as ArrayBlockingQueue can limit pending work; the application still needs a policy for rejection, waiting, or timeouts when full.

Checking isEmpty() and then removing an item is safe in our single thread example because nobody else changes the queue between those steps. Across threads, another consumer could remove that item first. Use the concurrent queue’s atomic operations and their results rather than relying on a separate check.

Conclusion

A queue represents pending work whose next item is determined by an access rule. For a FIFO queue, adding at the rear and removing at the front preserves arrival order. Circular arrays and linked nodes support those operations without repeatedly shifting every remaining item.

The breadth-first example shows why that order matters: children join behind nodes already waiting, so traversal finishes one level before moving to the next. When evaluating another use, ask what determines the next item, what happens when the queue is empty or full, and whether several threads access it. Then choose storage and coordination that support those requirements.

To practice, extend the traversal to return one list per level. At the start of each outer iteration, capture the queue’s current size and process exactly that many nodes. Their children form the next level, demonstrating how FIFO preserves the boundary between work already waiting and work just discovered.