Queue and Deque

Intuition

A queue is a line at a coffee shop: people join at the back and leave from the front, so the first to arrive is the first served (FIFO, first in, first out). The two core operations, enqueue (push to the back) and dequeue (pop from the front), are both O(1).

A deque (double-ended queue, pronounced "deck") allows inserting and removing at both ends in O(1). It is a stack and a queue at the same time, which makes it the most flexible linear container you will use in interviews.

Two implementation ideas are worth knowing because interviewers like to ask for them explicitly:

• Circular buffer. If you implement a queue on an array with a head and a tail index that only move right, the queue drifts toward the end of the array and "overflows" even though the front is empty. The fix is to wrap indices with % capacity, so slot 0 follows the last slot. That is a ring buffer, the standard way to build a fixed-capacity queue.
• Queue from two stacks. Push onto an inbox stack; pop from an outbox stack; when the outbox is empty, pour the whole inbox into it, which reverses the order so the oldest element ends up on top. Every element is pushed, moved and popped at most once, so each operation is O(1) amortized.

Language notes:

• Python: collections.deque gives O(1) append, appendleft, pop, popleft. Never use list.pop(0) as a dequeue: it shifts every element and costs O(n). queue.Queue is a thread-safe class with locks; it is slower and not meant for algorithms.
• Java: ArrayDeque (offer/poll/peek, plus offerFirst/pollLast and friends). Prefer it to LinkedList.
• C++: std::queue for a plain queue and std::deque when you need both ends or random access.

When to use it in interviews / OAs

• Breadth-first search. Shortest path in an unweighted graph or grid, level-order traversal of a tree, "minimum number of moves/steps/transformations". A queue processes states in order of distance, which is exactly why BFS finds shortest paths.
• Multi-source BFS. Several starting points spreading at the same speed (rotting fruit, distance to the nearest zero/exit). Put all sources in the queue at distance 0.
• Arrival-order processing and time windows. Simulating a printer or a task line, counting requests in the last 300 seconds, a rate limiter. Keep timestamps in a deque and pop expired ones from the front.
• Fixed-size buffers. "Design a circular queue", "moving average of the last k values".
• Both ends needed. Sliding windows that shrink from the left and grow on the right, palindrome checks, zigzag level order, 0-1 BFS, and the monotonic queue (separate article).

Template

BFS on a grid. Note that a cell is recorded when it is enqueued, not when it is dequeued; that guarantees each cell enters the queue once.

from collections import deque


def shortest_path(grid: list[str], start: tuple[int, int], goal: tuple[int, int]) -> int:
    # Fewest 4-directional steps from start to goal; '#' is a wall; -1 if unreachable.
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}  # Record a cell when it is enqueued, so it enters the queue once.
    q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return -1


maze = ["..#",
        ".##",
        "..."]
assert shortest_path(maze, (0, 0), (2, 2)) == 4
assert shortest_path(maze, (0, 0), (0, 1)) == 1
assert shortest_path([".#."], (0, 0), (0, 2)) == -1

Queue built from two stacks. The key rule: only refill the outbox when it is empty.

class TwoStackQueue:
    def __init__(self) -> None:
        self.inbox: list[int] = []  # Receives every push.
        self.outbox: list[int] = []  # Serves pops; the queue front is on its top.

    def push(self, x: int) -> None:
        self.inbox.append(x)

    def _refill(self) -> None:
        # Move items only when outbox is empty: each item moves at most once.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self) -> int:
        self._refill()
        return self.outbox.pop()

    def peek(self) -> int:
        self._refill()
        return self.outbox[-1]

    def __len__(self) -> int:
        return len(self.inbox) + len(self.outbox)


q = TwoStackQueue()
for x in (1, 2, 3):
    q.push(x)
assert q.pop() == 1
q.push(4)
assert [q.pop(), q.pop(), q.pop()] == [2, 3, 4] and len(q) == 0

Fixed-capacity ring buffer. Keeping a size counter is the simplest way to distinguish a full buffer from an empty one (both have the next write position equal to head).

class CircularQueue:
    def __init__(self, capacity: int) -> None:
        self.buf = [0] * capacity
        self.head = 0  # Index of the front element.
        self.size = 0  # Counting elements tells "full" apart from "empty".

    def enqueue(self, x: int) -> bool:
        if self.size == len(self.buf):
            return False
        self.buf[(self.head + self.size) % len(self.buf)] = x  # Wrap around past the end.
        self.size += 1
        return True

    def dequeue(self) -> int | None:
        if self.size == 0:
            return None
        x = self.buf[self.head]
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return x

    def front(self) -> int | None:
        return self.buf[self.head] if self.size else None

    def rear(self) -> int | None:
        return self.buf[(self.head + self.size - 1) % len(self.buf)] if self.size else None


cq = CircularQueue(3)
assert cq.enqueue(1) and cq.enqueue(2) and cq.enqueue(3) and not cq.enqueue(4)
assert cq.dequeue() == 1 and cq.enqueue(4)  # Slot 0 is reused.
assert cq.front() == 2 and cq.rear() == 4

For level-by-level processing (for example, returning each tree level as a list), read len(q) before an inner loop and pop exactly that many nodes; everything appended during the loop belongs to the next level.

Complexity

• Queue and deque operations at the ends: O(1). Deque random access in the middle (dq[i]) is O(n) in Python, so do not treat it like a list.
• BFS: O(V + E) time on a graph, O(rows * cols) on a grid; O(V) extra space for the queue and the visited set.
• Two-stack queue: O(1) amortized per operation, O(n) worst case for a single pop that triggers a refill. If the interviewer asks for worst-case O(1), say that a circular array or a linked list provides it.
• Ring buffer: O(1) worst case for every operation, O(capacity) space.

Common pitfalls

• list.pop(0) in Python. It is O(n); a BFS over 10^5 nodes becomes O(n^2) and times out. Use deque.popleft().
• Marking visited too late. Marking a node when you pop it lets the same node be enqueued many times (once per neighbor), which can blow up time and memory on dense graphs or grids.
• Mixing levels. If you need the depth, either store (node, depth) pairs or snapshot len(q) for each level. Do not recompute len(q) inside the loop.
• Full vs empty in a ring buffer. With only head and tail, both states look like head == tail. Track size, or leave one slot permanently unused.
• Refilling the outbox too eagerly. Pouring the inbox into the outbox while the outbox still has items breaks FIFO order.
• Forgetting the start state. In BFS, mark the source(s) as visited before the loop and handle "start equals goal".

Interview variations

• Level-order traversal and its relatives: right side view, zigzag order (append to the left or right of a per-level deque), average of each level.
• Grid BFS: shortest path in a binary matrix, knight moves, open-the-lock style state graphs (each state is a string or tuple), word ladder.
• Multi-source BFS: walls and gates, 01-matrix distances, rotting oranges.
• Design problems: circular queue/deque, hit counter, logger rate limiter, moving average from a data stream, recent calls counter.
• Implement a queue using stacks / a stack using queues. For the latter, after each push rotate the queue so the newest element is at the front.
• 0-1 BFS: when edge weights are only 0 or 1, use a deque, pushing 0-weight neighbors to the front and 1-weight neighbors to the back; it gives shortest paths in O(V + E) without a heap.
• Sliding window maximum with a monotonic deque (see the monotonic queue article).