Queue: Complete Guide with FIFO, Deque, and BFS Examples

Coding Patterns - Guide to 30 Core Algorithm Patterns

The Queue pattern is how you process a workload in the exact order it arrives. It shows up in breadth-first search on graphs and trees, in request and task pipelines, and in sliding window calculations where the oldest item must leave first. Interviewers reach for it constantly, and spotting when ordering matters more than priority is the skill the whole pattern tests.

Definition: a queue is a First-In-First-Out (FIFO) container. The element enqueued first is the one dequeued first. A queue exposes enqueue (append at the back), dequeue (remove from the front), and a way to peek at the front without removing it. FIFO ordering is the entire contract. Everything else in this pattern, the deque, the circular buffer, the monotonic queue, is a tuned version of that contract.

Real-World Analogy

Imagine a single cashier at a bakery on a busy morning. Customers join the line at the tail, the cashier serves whoever is at the head, and nobody gets served twice because they were once at the head. If a second cashier opens, the person at the front is still served next. That ordering never depends on how fast anyone walks, it depends only on arrival position.

Compare that with a load of plates in a cafeteria. Plates come off the top of the stack, so the plate placed last is used first. That is the LIFO stack pattern, and it is the mirror image of FIFO. Most interview mistakes on queue problems come from mixing these two orders up, so it helps to know which one you are simulating.

Visual Explanation

A queue is just a line moving left to right. Elements enter at the rear, and the front element is always next out.

    graph LR
    A["[]"] -->|"enqueue(5)"| B["[5]"]
    B -->|"enqueue(8)"| C["[5, 8]"]
    C -->|"enqueue(3)"| D["[5, 8, 3]"]
    D -->|"dequeue() = 5 rear advances"| E["[8, 3]"]
    E -->|"dequeue() = 8"| F["[3]"]

The front pointer jumps forward on each dequeue, and the rear pointer tracks where the next enqueue lands. When the two pointers meet, the queue is empty. That is the whole model. BFS, ring buffers, and monotonic deques are just this model with extra bookkeeping on the front or rear.

A BFS that returns the shortest number of steps shows the queue at work over a state space. Start node 0000, and each turn explores its neighbors in FIFO order:

    graph TD
    A["0000 (turns 0)"] --> B["1000, 0100, 0010, 0001 (turns 1)"]
    B --> C["all reachable neighbors, turns += 1"]
    C --> D["front of queue is always the earliest discovered state"]

Notice what the second diagram shows: depth is decided by position in the queue, not by any priority value. Whatever was enqueued first gets expanded first, so the first time a state pops, the number of steps recorded is the minimum possible.

When to Use This Pattern

The result depends on the arrival order of elements, and the problem asks for the first, oldest, or earliest of something. A structure must serve the earliest-arrived item next out.
You need the shortest path in an unweighted graph, or the minimum number of moves/operations to reach a target. That is BFS on a plain FIFO queue.
You need to process a tree or grid level by level, where all nodes at distance k are handled before distance k+1.
You need the maximum or minimum of every window as it slides forward, and a monotonic deque keeps candidates in order while discarding the useless ones.
You are building a bounded buffer of fixed capacity, where a circular array beats a linked list for cache behavior.

If the problem instead wants “latest first” or “most recent”, that is a stack. If it wants the “smallest weighted path” with costs, that is a priority queue (a heap) and belongs to the Heap/Priority Queue pattern.

Queue Variants You Will Meet

A few variants change how the front and rear behave, and interviewers mix them into problems without announcing them.

A stack-backed queue. When a problem says “implement a queue using two stacks”, you push into stack A, and when a dequeue or peek happens you drain stack A into stack B so the bottom of A becomes the top of B. The first push is the first popped. This is a queue hiding inside two LIFO containers, and each element moves between stacks at most once, so every operation is amortized constant time.

The deque (double-ended queue). The symmetric twin bundles a queue and a stack into one container. A Deque<int> supports push front, push back, pop front, and pop back in constant time. In sliding window maximum, the deque stores candidate values in decreasing order. The front, the largest, is the window maximum, and it is always in a position within the window, so every index is added and removed at most once.

The monotonic queue. A deque that discards elements as they become useless. When you append a value and the value at the back is smaller, that smaller value can never be the window maximum anymore, so pop it. The collection stays monotonically decreasing from front to back. Sliding window maximum is the canonical problem for this variant, listed on the practice problems page.

Complexity Analysis

The basic operations of the Queue pattern:

Operation	Time	Space	Notes
Enqueue at the rear	O(1)	O(N)	Appending at the tail is constant regardless of queue size
Dequeue at the front	O(1)	O(N)	Constant when a front pointer or a linked queue handles removal
Shift-based dequeue	O(N)	O(N)	`shift()` reindexes every remaining element
BFS traversal	O(V + E)	O(V)	V nodes and E edges, each enqueued once
Monotonic deque window	O(N)	O(K)	Each element enters and leaves the deque once, K is the window size

The queue stores at most one copy of each element, so space that comes with the queue itself is

O(N)

in the worst case, and queue operations are always

O(1)

in time when the front is visited via a pointer instead of a shifter.

Two cost traps to note. In JavaScript, queue.shift() on an Array reindexes every remaining element, so it turns the dequeue into

O(N)

and an entire BFS into

O(N^2)

for a tree. Use an index, a head pointer, or a linked queue instead. Second, a monotonic deque touches each element twice in the worst case, once when pushed and once when popped, so the sliding window maximum stays linear.

Memorizing complexity tradeoffs is half the battle. The other half is remembering them under pressure. Review this pattern with spaced repetition so the analysis becomes automatic by interview day.

Common Mistakes

Forgetting a “visited” set in BFS. Any graph or state space with cycles, and even in trees with shared children, when undiscovered nodes get enqueued again, the same state appears in the queue many times. The queue grows exponentially, and the loop never terminates. Mark a state visited the moment it is enqueued, not the moment it is popped. The first enqueue is the minimum distance, so later enqueues are duplicates.

Testing the size at dequeue but shrinking the queue at enqueue. Level-order traversal needs all nodes at one depth processed before the next. If you compute levelSize = queue.size() at dequeue time but modify the queue as you go, the limit shifts underneath you. Snapshot the size, then process exactly that many nodes, then snapshot again. Interviewers watch for this because it silently flattens levels.

Using the shift-based dequeue on an array. Languages with implicit queues (JavaScript, Ruby, Python lists) default to pushing and shifting. Every shift() is O(N), which turns a BFS whose total work is linear into one that is quadratic in the worst case. In interviews with deep trees, this difference comes up. Use deque in Python, Deque in Java, std::queue in C++, or head-pointer arithmetic.

Empty and full confusion on circular buffers. A circular buffer tracks head and size, and emptiness is size == 0 while fullness is size == cap. When a circular buffer uses only two pointers and compares them with head == tail, an empty queue and a full queue look identical. The standard fix is to keep a count alongside the pointers, because the two-pointer approach always collides at full capacity.

Deque frontier with stale window checks. Monotonic deques fail when the front-of-window check happens after the value should have been dropped. When the head index falls outside the current window and you read it before evicting it, you return an expired maximum. The two checks order in the template: evict out-of-window indices first, then the monotonicity pop, then push. Interviews ask the order for a reason.

These mistakes are expensive because they look correct until they fail on a hidden test case. Our review decks flag exactly these edge cases and drill them until they are reflex. Add this pattern to your queue .

Related Patterns

Stack . Queue is FIFO, Stack is LIFO. The two-stack queue problem is where they meet: the LIFO order of a stack becomes FIFO when you drain it twice.
Sliding Window . Sliding Window maintains a window with left and right indexes. The monotonic deque keeps the window’s extreme in O(1), and the window expiry is exactly the front index check.
Graph Traversal . BFS is the queue pattern applied to graphs, and the visited set is the queue’s companion.
Heap/Priority Queue . A priority queue replaces the “first in” rule with “smallest weight”, and it is where classic queue ordering breaks.
Topological Sort . Kahn’s algorithm processes nodes in zero in-degree order, which is exactly queue semantics over dependencies.

Next Steps

The intuition is only half the work. The code that turns it into memorized templates is the other half. Head to the code templates page , which implements FIFO, BFS, and monotonic deques in six languages, then move on to the practice problems to see the pattern applied to real interview questions.

Reading about a pattern once is not enough to own it in an interview. Practice this pattern with spaced repetition and turn recognition into recall.