Queues, Deques, and BFS Foundations | Developer Knowledge Base

Queues teach FIFO state flow, deques generalize that flow from both ends, and BFS turns a queue into a layer-by-layer exploration engine for shortest-step thinking and state expansion.

1. Definition

What is a queue?

A queue is a First-In, First-Out data structure. The earliest inserted element leaves first. Its core operations are typically enqueue, dequeue, peek, and isEmpty.

Why does it exist?

A queue exists because some processes must respect arrival order. That happens in scheduling, buffering, breadth-first exploration, level-order traversal, and state-expansion problems where earlier states must be processed before later ones.

What is a deque?

A deque is a double-ended queue. It supports insertion and removal at both ends, which makes it more flexible than a plain queue. It can model queue behavior, stack behavior, sliding window helper structures, and 0-1 BFS style transitions in more advanced topics.

What is BFS?

BFS stands for Breadth-First Search. It explores states level by level using a queue because the oldest frontier state must be processed before newer states. That preserves distance layers in unweighted settings.

Where does it fit?

This topic matters when the problem is about FIFO processing, level-order traversal, shortest number of steps in an unweighted setting, wave-like state expansion, or keeping a current window of candidates at either end.

Intuition

A queue is like a line at a ticket counter — the person who arrived first is served first. A deque is like a line that can be manipulated from both ends under controlled rules. BFS is like exploring a city one ring at a time: first you visit everything one step away, then everything two steps away, then everything three steps away. That layer ordering is the whole point.

Java context

In Java, Deque is also the standard API for queue behavior. A common implementation is:

Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(10);
queue.offerLast(20);
int first = queue.peekFirst();
int removed = queue.pollFirst();

For pure queue semantics, many candidates also use the Queue interface with ArrayDeque or LinkedList.

In interview solutions, ArrayDeque is usually the clean practical default unless null handling or a specific behavior changes the choice.

2. Core Concepts

2.1 FIFO behavior

The key rule is FIFO — earlier work is processed before later work. This is essential when order models time, distance, or fairness. Examples: customer line, task buffer, level-by-level traversal, shortest-step exploration.

2.2 Queue operations and complexity

Operation	Complexity	Meaning
enqueue / `offer`	`O(1)` amortized	Add at the back
dequeue / `poll`	`O(1)`	Remove from the front
front / `peek`	`O(1)`	Inspect front element
`isEmpty`	`O(1)`	Check whether work remains

2.3 Deque operations

A deque supports both ends with methods like offerFirst, offerLast, pollFirst, pollLast, peekFirst, and peekLast. This matters because many interview patterns are really "queue from one end, controlled cleanup from the other".

2.4 Why BFS needs a queue

BFS explores in increasing distance order. When you expand a state, all newly discovered states belong to the next layer and must wait behind all states of the current layer — that is exactly FIFO. If you accidentally use stack behavior, you drift toward DFS-like exploration and lose the layer guarantee.

2.5 Visited state matters

In BFS over graphs or general states, visited is often essential. Without it, the same state may be enqueued repeatedly, cycles may cause infinite processing, and complexity can explode. A strong default is to mark a state visited when you enqueue it, not when you dequeue it — that prevents duplicate enqueues.

2.6 Level-order traversal

A tree level-order traversal is one of the cleanest BFS forms. The queue stores nodes waiting to be processed, and children are added behind the remaining nodes of the current layer, naturally producing level-by-level output.

2.7 Distance interpretation

In an unweighted graph or state space, BFS discovers the shortest path in terms of edge count or step count. All layer-0 states are processed first, then layer-1, then layer-2, and so on — the first time you reach a node is therefore the shortest distance.

2.8 Multi-source BFS

Sometimes BFS starts from many initial states at once — you simply enqueue all starting states first. This is common in nearest zero / nearest source problems, contamination spread simulations, and fire or infection timing models.

2.9 Queue size and layer processing

A common BFS pattern is: measure current queue size, process exactly that many nodes, then increment depth. That is how you keep layer boundaries explicit.

2.10 Recognition signals

Queue or BFS thinking should trigger when you see:

shortest number of moves in an unweighted problem,
level-order traversal,
process in arrival order,
spread outward from a source,
all neighbors of current states,
or “minimum steps” with uniform transition cost.

2.11 Queue vs deque recognition

Use a deque when:

you need both ends,
you need a sliding-window helper,
you want queue and stack behavior from the same structure,
or a variant such as monotonic deque appears later.

3. Practical Usage

When to use a queue

A queue is right when the oldest pending item should go first.

Typical situations:

request handling,
producer-consumer buffering,
BFS frontier processing,
tree level traversal,
shortest-step problems with equal edge weights.

When to use a deque

A deque is strong when the problem needs controlled behavior from both ends.

Examples:

implementing both stack and queue semantics,
sliding window maximum patterns,
keeping candidates in order while trimming outdated ones,
or structured front/back processing.

When BFS is the right idea

BFS is usually the right pattern when the question sounds like:

“What is the minimum number of steps?”
“What is the shortest path in an unweighted graph?”
“Traverse level by level.”
“How long until this effect reaches all nodes?”

When NOT to use BFS

BFS is not the natural choice when:

the structure is deep and you only need one path,
weighted shortest path is involved,
recursion or DFS is simpler for full traversal,
or the problem is not about layer distance at all.

Java-specific guidance

For most interview queue and BFS code, ArrayDeque is the default.

It gives efficient front and back operations.

The LinkedList class can also implement Queue or Deque, but for most algorithm problems ArrayDeque is cleaner and usually preferred.

Pair-programming angle

A strong explanation sounds like this:

“This is minimum steps in an unweighted state space, so BFS is a good fit.”
“I will enqueue the start state, mark visited immediately, and expand layer by layer.”
“The first time I reach the target is optimal because BFS preserves distance order.”

That explanation is much stronger than "I'll just use a queue."

LeetCode #102 — Binary Tree Level Order Traversal — textbook BFS with level tracking.
LeetCode #994 — Rotting Oranges — multi-source BFS on a grid.
LeetCode #1091 — Shortest Path in Binary Matrix — BFS for minimum steps.
LeetCode #542 — 01 Matrix — multi-source BFS from all zeroes simultaneously.
LeetCode #239 — Sliding Window Maximum — monotonic deque for range maximum.

4. Code Examples

Basic Example

This demonstrates plain queue behavior.

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

public class QueueBasicsExample {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();

        queue.offerLast("first");
        queue.offerLast("second");
        queue.offerLast("third");

        while (!queue.isEmpty()) {
            System.out.println(queue.pollFirst());
        }
    }
}

The output order matches insertion order.

That is FIFO in action.

Advanced Example

This uses BFS for binary tree level-order traversal.

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

public class LevelOrderTraversalExample {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value) {
            this.value = value;
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offerLast(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int count = 0; count < levelSize; count++) {
                TreeNode current = queue.pollFirst();
                currentLevel.add(current.value);

                if (current.left != null) {
                    queue.offerLast(current.left);
                }
                if (current.right != null) {
                    queue.offerLast(current.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }
}

Why it works:

the queue contains the current frontier,
levelSize locks the current layer,
children get queued for the next layer.

Common Pitfall

This is a classic BFS bug pattern.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class BrokenBfsIdea {
    public static void broken(int start, int[][] graph) {
        Deque<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();

        queue.offerLast(start);

        while (!queue.isEmpty()) {
            int current = queue.pollFirst();

            for (int neighbor : graph[current]) {
                if (!visited.contains(neighbor)) {
                    queue.offerLast(neighbor);
                }
            }

            visited.add(current);
        }
    }
}

Why this is risky:

a node may be enqueued multiple times before it is finally dequeued,
duplicates waste work,
and in dense graphs the queue can grow unnecessarily.

A stronger default is to mark visited when you enqueue.

Another useful pattern: minimum steps on a grid

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

public class GridBfsExample {
    static class State {
        int row;
        int col;
        int distance;

        State(int row, int col, int distance) {
            this.row = row;
            this.col = col;
            this.distance = distance;
        }
    }

    public static int shortestPath(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (grid[0][0] == 1) {
            return -1;
        }

        boolean[][] visited = new boolean[rows][cols];
        Deque<State> queue = new ArrayDeque<>();
        queue.offerLast(new State(0, 0, 0));
        visited[0][0] = true;

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            State current = queue.pollFirst();

            if (current.row == rows - 1 && current.col == cols - 1) {
                return current.distance;
            }

            for (int[] direction : directions) {
                int nextRow = current.row + direction[0];
                int nextCol = current.col + direction[1];

                boolean inBounds = nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols;
                if (!inBounds || grid[nextRow][nextCol] == 1 || visited[nextRow][nextCol]) {
                    continue;
                }

                visited[nextRow][nextCol] = true;
                queue.offerLast(new State(nextRow, nextCol, current.distance + 1));
            }
        }

        return -1;
    }
}

This is a standard BFS template for minimum-step state expansion.

5. Trade-offs

Aspect	Details
⚡ Performance	Queue operations are constant time, and BFS gives shortest-step answers efficiently in unweighted settings
💾 Memory	BFS can require large frontier storage; visited structures also add memory overhead
🔧 Maintainability	Clean when frontier, visited, and layer semantics are explicit; messy when state encoding is unclear
🔄 Flexibility	Excellent for traversal, scheduling, wave propagation, and shortest-step exploration

Performance nuance

BFS is powerful because it avoids re-solving the same shallow states repeatedly.

But it can still be memory-heavy if the frontier grows wide.

That is the classic breadth trade-off.

Memory nuance

Compared with DFS, BFS often stores more simultaneous states.

That is acceptable when the shortest-path guarantee matters.

But it is a real cost.

Readability nuance

BFS code stays clean when three things are obvious:

what the state is,
when something becomes visited,
and what one queue layer means.

6. Common Mistakes

Using the wrong data structure — If you accidentally use stack behavior, you lose BFS layer ordering.
Marking visited too late — Marking only on dequeue can enqueue duplicates and waste work.
Forgetting layer semantics — If the question is about depth or distance, you must track layers or distances explicitly.
Encoding too little state — Some BFS problems need more than position; they may also need keys, direction, remaining budget, or parity.
Using BFS on weighted shortest-path problems — BFS assumes uniform edge cost. Weighted graphs usually need a different algorithm.
Ignoring bounds and blockers — Grid BFS often fails on boundary checks and obstacle handling, not on the queue logic itself.
Confusing queue and deque roles — A deque can act as a queue, but the chosen end operations must still match the intended semantics.

Debugging tip

For a small input, log each queue layer.

If nodes appear in the wrong distance order, the enqueue or visited timing is probably wrong.

7. Deep Dive

Why BFS gives shortest paths in unweighted problems

Because it explores by distance layers.

All states at distance d are processed before any state at distance d + 1.

So the first arrival at a target is automatically optimal in step count.

That is the deepest idea in BFS.

BFS is really frontier management

Another useful mental model:

BFS maintains a frontier of states that are known but not yet expanded.

The queue is that frontier in time order.

This is why BFS feels like wave propagation.

Multi-source BFS is underused by many candidates

A lot of problems become simpler if you start from every valid source at once.

Examples include:

nearest facility,
spread timing,
shortest distance to any source.

If the problem asks distance to the nearest one of many starts, multi-source BFS should be considered early.

Deques lead into stronger later patterns

This chapter only introduces deques at the foundation level.

But later they reappear in:

sliding window maximum,
monotonic deque patterns,
0-1 BFS,
and advanced scheduling/state pruning ideas.

So even if a problem seems “just queue-based”, learning the deque API now pays off later.

BFS vs DFS communication

A strong engineer does not just know both.

They know why one is better.

For example:

BFS if minimum number of edges matters,
DFS if full structural exploration is enough and memory profile matters more,
queue when order must reflect arrival or level,
stack when the newest unresolved item matters.

Pair-programming scenario

Imagine a grid shortest-path problem.

A strong explanation is:

the grid is unweighted,
each move costs one step,
BFS preserves shortest-step order,
visited prevents duplicates,
and the first time we reach the target is optimal.

That is concise, correct, and reassuring to a teammate or interviewer.

8. Interview Questions

Q: Why is BFS the standard answer for shortest path in an unweighted graph? — A: Because BFS explores nodes layer by layer in increasing edge distance, so the first time a node is reached is the shortest path to it.

Q: Why should visited usually be marked when enqueuing, not dequeuing? — A: Because early marking prevents the same state from being enqueued multiple times by different parents.

Q: What is the practical difference between a queue and a deque? — A: A queue uses one end for insertion and the other for removal, while a deque supports both ends for both operations.

Q: When is BFS a bad fit? — A: When edge weights differ, when shortest-step ordering is irrelevant, or when depth-first exploration is simpler and sufficient.

Q: Why is ArrayDeque usually preferred in Java interview code? — A: Because it efficiently supports front/back operations and gives clean queue and deque semantics without the legacy baggage of older APIs.

9. Glossary

Term	Definition
FIFO	First-In, First-Out behavior where the earliest element is removed first
frontier	The set of discovered but not yet processed BFS states
level-order traversal	A traversal that processes nodes layer by layer from top to bottom
state expansion	Generating neighboring states reachable from the current state
multi-source BFS	BFS that starts from many initial states at the same time
deque	A double-ended queue supporting insertion and removal on both ends

10. Cheatsheet

Use a queue when the oldest pending item must go first.
Use ArrayDeque as the default queue/deque implementation in Java interview code.
BFS is the right first guess for minimum steps in an unweighted state space.
Mark visited when enqueuing unless you have a specific reason not to.
Level-order traversal is BFS on trees.
A deque supports both ends and becomes important in later sliding-window patterns.
If edge costs are not uniform, plain BFS may be the wrong tool.
Be explicit about what one BFS state contains.
If the answer is distance by layers, queue semantics are usually essential.
The first time BFS reaches a target in an unweighted problem is usually the optimal step count.