Queues and Deques

1The mental model (what this really is)#

Two shapes, two different jobs. Keep them straight and most of the pattern falls out.

A queue is a line at a coffee shop.

• First person in line gets served first: FIFO, first in, first out.
• You add to the back (enqueue) and remove from the front (dequeue).
• Both operations are O(1) when you back it with a doubly linked list or a ring buffer.
• A stack is the opposite (LIFO), but we are not here for that.

A deque is a line where people join or leave from either end.

• Pronounced "deck," short for double-ended queue.
• Front or back, both are fair game, both in O(1).
• It is the Swiss Army version: acts like a queue, acts like a stack, or does things neither can.
• In Python it is collections.deque, in Java ArrayDeque, in C++ std::deque or a manual two-pointer array.

The one insight worth tattooing on your brain.

• A queue preserves the order things arrived and lets you process the oldest first.
• So "oldest unprocessed thing," "nearest first," or "level by level" all point at a queue.
• For a deque the insight is different: you want O(1) at both ends.
• The moment you think "I need the newest item AND the oldest item cheaply," reach for a deque.
• The classic payoff: turning an O(n log k) heap solution into a clean O(n) one.

2How to recognize it (the signals in a problem)#

Train your eye for these. You have maybe thirty seconds to pattern-match before you start talking, and naming the pattern out loud buys you time to write clean code.

Reach for a queue when you see:

• "Shortest path" or "fewest steps" in an unweighted graph or grid. That is BFS. The unweighted part is the tell. The moment edges have different weights, you want Dijkstra and a heap instead.
• "Level by level," "layer," "nearest," "spreading outward" (rot spreading, fire spreading, flood fill by distance).
• Processing tasks or events in arrival order: scheduling, buffering, producer/consumer.
• Anything that says "in order" and "one at a time."

Reach for a deque when you see:

• A sliding window where you need the max or min of the current window. This is the big one: the monotonic deque. It shows up constantly and is the single most valuable deque trick to own.
• "Most recent" and "oldest" both matter, like a cache or a running window.
• You want a structure that is a queue sometimes and a stack other times.
• Palindrome checks where you compare both ends moving inward.

3The template (how it works, with pseudocode)#

Here is the plain queue, the one you use for BFS. Burn this into muscle memory. I can write this version in under a minute now, and that speed is what lets me spend the saved time on edge cases.

function bfs(start):
  queue = new Queue()
  visited = set()
  queue.push(start)
  visited.add(start)

  while queue is not empty:
    node = queue.pop_front()          # take the oldest
    process(node)
    for neighbor in neighbors(node):
      if neighbor not in visited:
        visited.add(neighbor)         # mark on PUSH, not on pop
        queue.push(neighbor)

The one deliberate choice above:

• Mark a node visited when you push it, not when you pop it.
• Mark on pop and the same node can get pushed five times before you ever process it.
• That bug is slow and sometimes wrong. Mark on push.

If you need level information (how many steps from start), wrap each level in a count:

level = 0
while queue is not empty:
  size = queue.length                 # snapshot this level's size
  for i in range(size):
    node = queue.pop_front()
    ... process ...
    for neighbor in neighbors(node):
      if unvisited: mark and push
  level += 1                          # one full level done

Why the snapshot is the whole trick:

• Freeze how many nodes belong to the current level, then drain exactly that many.
• Everything you push during the loop belongs to the next level.
• Skip the snapshot and the inner loop reads a length that keeps growing as you push.
• The level boundaries dissolve and your distances go wrong.

Now the monotonic deque, for sliding window max:

function sliding_window_max(nums, k):
  dq = new Deque()                    # will hold INDICES, kept decreasing by value
  result = []
  for i in range(len(nums)):
    # drop indices that fell out of the window on the left
    if dq not empty and dq.front() <= i - k:
      dq.pop_front()
    # drop smaller values from the back, they can never be the max
    while dq not empty and nums[dq.back()] <= nums[i]:
      dq.pop_back()
    dq.push_back(i)
    if i >= k - 1:
      result.append(nums[dq.front()])
  return result

The invariant that makes it click:

• Store indices, not values, so you can tell when something aged out of the window.
• The deque values stay in decreasing order, so the front is always the max of the current window.
• That is the whole trick. State it in one sentence and you have shown the interviewer you understand it.

4A worked example (walk through one problem step by step)#

Let me walk the classic grid BFS: shortest path in a maze (or "number of steps to reach the exit"). Grid where 0 is open, 1 is a wall, start top-left, want bottom-right, moving up/down/left/right.

Why a queue and not a stack:

• BFS explores in rings: everything one step away, then everything two steps away, and so on.
• The first time BFS touches the exit, it did so by the shortest possible number of steps.
• No other path could have reached it sooner, because BFS never skips a closer ring to go further.
• A stack would dive deep down one corridor and could reach the exit by a long, winding route before it checks the short one.

Here is my thinking out loud:

1. Seed the queue. Put the start cell in, distance 0, mark it visited.
2. Pop the oldest cell. Say it is (0,0) at distance 0.
3. Look at its four neighbors. For each one in bounds, not a wall, not yet visited: mark it visited, give it distance 0 + 1 = 1, push it to the back.
4. Loop. The queue now holds all distance-1 cells. Pop each, their unvisited neighbors become distance 2 pushed to the back. New cells always go to the back and we always pop the front, so every distance-1 cell is processed before any distance-2 cell. That is FIFO doing the heavy lifting.
5. Stop when you pop the exit. The distance stored on it is the answer.
6. If the queue empties and you never saw the exit, it is unreachable. Return -1 or whatever the problem wants.

Make the ordering concrete.

• After seeding, the queue is [(0,0,d=0)].
• Pop (0,0), push neighbors: [(0,1,d=1), (1,0,d=1)].
• Pop (0,1), push its new neighbors at d=2: [(1,0,d=1), (0,2,d=2), (1,1,d=2)].
• See how (1,0) at distance 1 is still ahead of the distance-2 cells? It gets processed next.
• The queue keeps closer cells in front. You never sort anything and never need a heap, because every edge costs exactly 1.

Why "mark on push" matters here too.

• If two distance-1 cells both border the same distance-2 cell, the first to reach it marks it.
• The second sees it is already visited and skips it.
• Without that, you enqueue the same cell twice and waste work, or worse, overwrite its distance with a larger value.

Complexity of this walk:

• Every cell is pushed and popped at most once, and we look at four neighbors per cell.
• So O(rows * cols) time, O(rows * cols) space for the visited set and the queue in the worst case.
• For a 1000 by 1000 grid that is about a million cells, which runs well inside a one-second limit.
• A naive DFS that re-walks paths could blow past that by orders of magnitude.

5Variations and gotchas#

The interviewer rarely asks the vanilla version. Here are the twists that come after "nice, now what if."

Multi-source BFS.

• Seed the queue with several starting cells at distance 0. Everything else is identical.
• This is how you solve "rotting oranges" or "how long until the whole grid is on fire."
• You do not run BFS once per source. You run it once with all sources in the queue at the start.
• That turns a potential O(sources * cells) into a single O(cells) pass. Interviewers love when you spot it.

0-1 BFS.

• When edges cost either 0 or 1, you can skip a full priority queue.
• Use a deque: push 0-cost moves to the front, 1-cost moves to the back.
• This keeps the deque sorted by distance for free and runs in O(V + E) instead of the O(E log V) you would pay with a heap.
• Niche but it impresses.

Queue built from two stacks (or a stack from two queues).

• A classic "implement X using Y" question.
• Queue from two stacks: one stack for incoming, one for outgoing.
• When you need to dequeue and the outgoing stack is empty, pour everything from incoming into outgoing (which reverses the order, giving you FIFO).
• Each element moves between stacks at most once, so it is amortized O(1) even though a single dequeue can occasionally be O(n).

Circular queue / ring buffer.

• Fixed-size queue using an array and two pointers that wrap around with modulo.
• All operations are O(1) and there is zero shifting.
• Shows up in streaming and "design a buffer" questions.
• Under the hood it is how real queue libraries avoid the pop(0) trap below.

Gotchas that bite people:

• Forgetting the queue can hold duplicates if you mark visited on pop.
• Reading queue.length inside the level loop instead of snapshotting it first. The length changes as you push, and your level boundaries dissolve.
• In the monotonic deque, using < versus <= when popping the back. Get it wrong and you mishandle equal values. With <= you evict equal elements, which is fine for a plain max but changes behavior if the problem counts distinct indices. Think about whether duplicates should stay.
• Using a plain list/array and calling pop(0) in Python. That is O(n) because it shifts everything. Use collections.deque. This single mistake turns an O(n) solution into O(n squared) and times out, often on the very last hidden test case.

6Complexity#

Know these cold and say them out loud when you pick your structure.

BFS with a proper queue:

• Time: O(V + E) for graphs, O(rows * cols) for grids. Each node enqueued and dequeued once, each edge examined once.
• Space: O(V) worst case. A wide graph can hold most of a level in the queue at once. For a grid, the widest front is the diagonal, so still O(rows * cols) in the worst case.

Monotonic deque (sliding window):

• Time: O(n). Each index is pushed once and popped at most once across the whole run. It looks like a nested loop, but the inner while is amortized O(1). Beating the heap approach here is O(n) versus O(n log k).
• Space: O(k), the window can hold at most k indices.

Core queue/deque operations themselves:

• push, pop from either end, peek: all O(1) with the right underlying structure (linked list or a proper deque implementation).
• Saying this out loud tells the interviewer you know why the overall bound holds.

7Mistakes that cost people the round#

The bugs below are the difference between a pass and a "let's move on."

1. Marking visited on pop instead of push. The number-one BFS bug. It still produces correct answers sometimes, which is why it is sneaky, but it blows up time complexity and fails on larger graphs where one node gets enqueued many times.
2. list.pop(0) in Python. O(n) per op. Your "O(V+E)" solution is secretly quadratic and the interviewer knows. Say "I'll use a deque for O(1) pops" out loud and you defuse it before it bites.
3. Confusing when to use a queue versus a stack. BFS needs a queue (FIFO). DFS uses a stack or recursion (LIFO). Swapping them gives wrong shortest paths because DFS has no distance guarantee.
4. Not snapshotting level size, so level-by-level logic silently breaks and your per-level counts drift.
5. Reaching for a heap when a deque would do. On "sliding window max," a heap gives O(n log k) and the deque gives O(n). Interviewers at the bar-raiser level want the deque, and some will push back if you stop at the heap.
6. Storing values instead of indices in the monotonic deque, then being unable to tell when an element left the window.
7. Over-explaining the easy part, under-explaining the invariant. For the deque, the thing worth saying is "the deque stays decreasing, so the front is always the window max." State the invariant. That is what separates a pass from a strong pass.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one adds exactly one new idea. Resist jumping ahead, because the deque problems assume the BFS reflex is already automatic.

Warm-up (build the reflex):

• Implement Queue using Stacks
• Implement Stack using Queues
• Design Circular Queue
• Number of Recent Calls

Core BFS (the bread and butter):

• Binary Tree Level Order Traversal
• Flood Fill
• Number of Islands (BFS version)
• Rotting Oranges (your first multi-source)
• 01 Matrix (multi-source distance)

Level up:

• Word Ladder
• Open the Lock
• Shortest Path in Binary Matrix
• Walls and Gates
• Perfect Squares (BFS framing)

Deque specialists:

• Sliding Window Maximum (the canonical monotonic deque)
• Shortest Subarray with Sum at Least K
• Jump Game VI
• Design Front Middle Back Queue

If you only have an hour:

• Do "Binary Tree Level Order Traversal" and "Rotting Oranges" until you can write them without thinking.
• Then do "Sliding Window Maximum" until the monotonic deque feels natural.
• Those three carry most of the pattern, and they are the hour well spent.

Name the pattern out loud in the first thirty seconds, and the code almost writes itself.

9Where this shows up (which companies and rounds lean on it)#

A quick map of where the pattern actually lands in a loop.

• BFS and level-order traversal are staples of the standard coding round at basically every large company.
• Grid problems (islands, rotting oranges, shortest path in a matrix) are extremely common phone-screen material, the kind you get in a 45-minute first screen.
• The sliding window max / monotonic deque shows up more in the harder on-site rounds and at companies that push algorithmic depth, where the heap solution gets you a "can you do better?" follow-up.
• "Implement a queue using stacks" and "design a circular buffer" turn up in both coding and the occasional low-level/systems screen.
• If you are interviewing anywhere that does a graph round, you will touch a queue.

Want to see exactly which rounds at which companies lean on queues and BFS? Check the company guides to map this pattern to the interviews you are actually prepping for.