Queues

A queue is a collection with the opposite rule from a stack: the first thing you put in is the first thing you take out (FIFO — first in, first out). Think of a physical line at a coffee shop: whoever joined first gets served first, new arrivals join at the back, and nobody can cut in the middle. Interviewers care about queues because "process things in the order they arrived" is one of the most common real requirements in systems: a print spooler, a task/job scheduler, a message broker, a web server's request buffer, and — inside algorithms rather than systems — breadth-first search, which explores a graph level by level precisely because it uses a queue instead of a stack. Get comfortable with queues and you'll recognize the pattern the moment "process in arrival order" or "level by level" shows up in a problem statement.

Deep Dive: FIFO and the "False Overflow" Problem

If a queue is implemented naively — front and rear are indices that only ever move forward, and dequeue just increments front — then every dequeue permanently "wastes" the slot at the old front; it's never reused. After enough enqueue/dequeue cycles, rear can hit the end of the array while most of the array is actually empty space to the left of front. The queue reports "full" when it's really mostly empty. This is the false overflow problem, and it's exactly the kind of subtle bug an interviewer wants to see you catch before you write the code, not after.

Deep Dive: The Circular Queue Fix

def enqueue(self, x):
    if self.size == self.capacity:
        raise OverflowError("queue full")
    tail = (self.head + self.size) % self.capacity
    self.data[tail] = x
    self.size += 1

def dequeue(self):
    if self.size == 0:
        raise IndexError("queue empty")
    x = self.data[self.head]
    self.head = (self.head + 1) % self.capacity
    self.size -= 1
    return x

A circular (ring) queue fixes this by treating the underlying array as a circle: instead of a fixed rear index that only grows, the next write position is computed as (head + size) % capacity, and dequeue advances head the same way: (head + 1) % capacity. The modulo operator is what makes an index wrap from capacity - 1 back to 0, so freed slots at the front get reused by later enqueues instead of sitting empty forever. The queue is genuinely full only when size == capacity — tracked with an explicit size counter (or by sacrificing one slot as a sentinel) — not when a raw index happens to reach the end of the array.

Deep Dive: Priority Queue as an Abstract Data Type

A priority queue is defined purely by its contract, not by any implementation: "the next item removed is always the one with the highest priority currently in the collection," regardless of insertion order. That's a completely different guarantee from FIFO — a plain queue promises order-of-arrival, a priority queue promises order-of-importance and explicitly ignores arrival order. You could implement a priority queue with an unsorted array (O(1) insert, O(n) to find-and-remove the max), a sorted array (O(n) insert, O(1) remove), or — the standard choice — a binary heap, which gets O(log n) for both insert and remove-highest-priority. The heap is an implementation detail; the ADT contract is what makes something a priority queue. The full mechanics of building one efficiently belong on the heaps page — the point here is just to not confuse "priority queue" (the contract) with "heap" (the usual way to fulfill it), since interviewers will sometimes ask you to justify that pairing rather than assume it.

Deep Dive: Deque and Restricted Variants

A deque (double-ended queue) relaxes the "one end only" rule of both stacks and queues: you can push and pop from either end in O(1). It's a strict superset — you can use a deque to act as a stack, a queue, or both at once. Two restricted variants show up in interview vocabulary: an input-restricted deque only allows insertion at one end (but removal at both), and an output-restricted deque only allows removal at one end (but insertion at both). The canonical deque application is the sliding-window-maximum pattern: maintain a deque of indices with strictly decreasing values, drop indices that fall outside the current window from the front, and drop indices from the back whenever a new, larger value arrives (they can never be the max of any future window that still contains the new value) — each index is pushed and popped at most once, so the whole scan is O(n), the same amortized argument used for the monotonic stack on the stacks page.

Deep Dive: Building a Queue from Two Stacks (and a Stack from Two Queues)

def enqueue(self, x):
    self.in_stack.append(x)

def dequeue(self):
    if not self.out_stack:
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())
    return self.out_stack.pop()

Two stacks can emulate a queue: push every enqueue onto in_stack. To dequeue, if out_stack is empty, pop everything off in_stack and push it onto out_stack — this reversal is exactly what turns "most recently pushed on top" into "oldest element on top," recovering FIFO order from two LIFO stacks. Then pop from out_stack. The reason this works: an element only gets moved from in_stack to out_stack once in its entire lifetime, so even though a single dequeue can occasionally trigger an O(n) drain, each element is moved at most once total across all operations — amortized O(1) per operation, the same amortized-cost reasoning as a dynamic array's doubling.

The reverse — a stack from two queues — is possible but rarely useful in practice: to push, enqueue into an empty q2, then dequeue everything from q1 into q2 so the new element ends up at the front, then swap q1 and q2's names; this makes push O(n) instead of pop, the opposite trade-off from the two-stack queue. It's asked occasionally as a "do you actually understand both ADTs, not just memorized the popular direction" check, not because it's a pattern you'll reach for on the job.

Key Pointers

• FIFO: enqueue at the back, dequeue from the front — the element that arrived first leaves first.
• A naive array queue with a forward-only front index "runs out of space" even when mostly empty, because dequeued slots are never reused — the false overflow problem.
• A circular queue fixes it with modular arithmetic: the next index is (start + size) % capacity, so freed front slots wrap around and get reused.
• A priority queue is an ADT contract ("highest priority out first"), not an implementation — a heap is just the efficient (O(log n)) way to build one.
• A deque allows O(1) push/pop at both ends and is a strict superset of both stack and queue behavior; it's the right tool for sliding-window problems.
• A queue can be built from two stacks with amortized O(1) operations, because each element is transferred between the two stacks at most once in its lifetime.
• BFS uses a queue specifically because it needs to explore level by level — visiting all distance-1 nodes before any distance-2 node — which is a FIFO guarantee, not a LIFO one.
• Using a stack where BFS needs a queue silently turns the traversal into something DFS-like, breaking any shortest-path or level-by-level guarantee without necessarily crashing.

How It Works

1. Maintain two references: the front (next to dequeue) and enough information to compute the next enqueue position (a rear index, or front + size).
2. enqueue(x): place x at the computed rear position and increase the size (in a circular array, tail = (head + size) % capacity; in a linked-list queue, append a node and update the tail pointer).
3. dequeue(): read the value at the front, advance the front reference (head = (head + 1) % capacity, or move to the next linked node), decrease the size, and return the value.
4. Check capacity before enqueue (size == capacity) and emptiness before dequeue (size == 0) — both are O(1) with a maintained size counter.
5. For a deque, apply the same enqueue/dequeue logic independently at both ends, each in O(1).
6. For BFS: enqueue the start node, mark it visited; while the queue isn't empty, dequeue a node, process it, and enqueue every unvisited neighbor, marking each visited at enqueue time (not at dequeue time, to avoid enqueueing duplicates).
7. For the two-stack queue: enqueue always pushes onto in_stack; dequeue pops from out_stack, refilling it from in_stack only when it's empty.

Try It Yourself

A fixed-capacity circular queue using modular arithmetic, and a FIFO queue built from two stacks.

class CircularQueue:
    """Fixed-capacity array queue using modular arithmetic so freed slots at the front are reused."""
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = [None] * capacity
        self.head = 0   # index of the front element
        self.size = 0

    def enqueue(self, x):
        if self.size == self.capacity:
            raise OverflowError("queue full")
        tail = (self.head + self.size) % self.capacity
        self.data[tail] = x
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("queue empty")
        x = self.data[self.head]
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return x

    def snapshot(self):
        return [self.data[(self.head + i) % self.capacity] for i in range(self.size)]


class QueueFromTwoStacks:
    """FIFO built from two LIFO stacks: in_stack absorbs pushes, out_stack serves pops in FIFO order."""
    def __init__(self):
        self.in_stack = []
        self.out_stack = []
        self.transfers = 0

    def enqueue(self, x):
        self.in_stack.append(x)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
                self.transfers += 1
        return self.out_stack.pop()


cq = CircularQueue(4)
for x in [10, 20, 30, 40]:
    cq.enqueue(x)
print("after 4 enqueues        :", cq.snapshot(), "head index =", cq.head)
print("dequeue ->", cq.dequeue(), " dequeue ->", cq.dequeue())
print("after 2 dequeues        :", cq.snapshot(), "head index =", cq.head, "size =", cq.size)
cq.enqueue(50)
cq.enqueue(60)
print("after enqueue 50,60     :", cq.snapshot(), "head index =", cq.head)
try:
    cq.enqueue(70)
except OverflowError as e:
    print("enqueue 70 ->", e, "(size == capacity == 4)")

q = QueueFromTwoStacks()
for x in [1, 2, 3]:
    q.enqueue(x)
print("in_stack after 3 enqueues:", q.in_stack, " out_stack:", q.out_stack)
print("dequeue ->", q.dequeue(), " (transfers so far:", q.transfers, ")")
print("in_stack:", q.in_stack, " out_stack:", q.out_stack)
q.enqueue(4)
print("enqueue 4 -> in_stack:", q.in_stack, " out_stack:", q.out_stack)
print("dequeue ->", q.dequeue(), " dequeue ->", q.dequeue(), " dequeue ->", q.dequeue())
print("total transfers across all dequeues:", q.transfers, "(each element moved exactly once)")

# Output:
# after 4 enqueues        : [10, 20, 30, 40] head index = 0
# dequeue -> 10  dequeue -> 20
# after 2 dequeues        : [30, 40] head index = 2 size = 2
# after enqueue 50,60     : [30, 40, 50, 60] head index = 2
# enqueue 70 -> queue full (size == capacity == 4)
# in_stack after 3 enqueues: [1, 2, 3]  out_stack: []
# dequeue -> 1  (transfers so far: 3 )
# in_stack: []  out_stack: [3, 2]
# enqueue 4 -> in_stack: [4]  out_stack: [3, 2]
# dequeue -> 2  dequeue -> 3  dequeue -> 4
# total transfers across all dequeues: 4 (each element moved exactly once)

Common Mistakes & Interview Traps

• Implementing an array queue with a forward-only front/rear index and being surprised it reports "full" while mostly empty — that's the false-overflow bug; use a circular index or a linked-list queue.
• Distinguishing "empty" from "full" in a circular queue using only head == tail — both states can produce that condition; track an explicit size counter (or deliberately waste one slot) to disambiguate.
• Assuming a priority queue is a FIFO structure because "queue" is in the name — it explicitly ignores arrival order in favor of priority order; only ties are typically broken by arrival order, and only if you implement it that way.
• Using BFS's queue like a stack by accident (e.g. inserting at the wrong end, or using .pop() instead of .pop(0)/popleft() on a list) — this silently turns level-order traversal into something DFS-like and breaks the shortest-path guarantee without an obvious error.
• Using Python's list.pop(0) for dequeue — it's O(n) because every remaining element shifts left; use collections.deque, which is a genuine doubly-linked structure with O(1) operations at both ends.
• Marking BFS nodes visited at dequeue time instead of enqueue time — this lets the same node get enqueued multiple times before it's first processed, wasting work and, in graphs with cycles, potentially causing incorrect results.

Interview Q&A

Q: Why does a naive array-based queue "run out of space" even when it isn't actually full?

A: If dequeue only ever advances a front index forward and never reclaims the vacated slots, then after repeated enqueue/dequeue cycles the rear index can reach the end of the physical array while most of the array to the left of the front is empty. The queue reports full based on the rear index hitting the array boundary, not based on how many elements are actually stored — that's the false-overflow problem.

Q: How does a circular queue fix that, and what's the modular-arithmetic trick?

A: It computes the next write and read positions with index % capacity instead of letting them grow unbounded, so index capacity - 1 wraps back around to index 0. Concretely, tail = (head + size) % capacity for the next enqueue slot and head = (head + 1) % capacity after each dequeue — this lets freed slots at the front be reused by later enqueues, and the queue is genuinely full only when a maintained size counter equals capacity.

Q: What's the difference between a queue and a priority queue as abstract data types?

A: A queue's contract is "the element removed next is whichever was inserted first" — pure arrival order. A priority queue's contract is "the element removed next is whichever currently has the highest priority," regardless of when it was inserted; a low-priority item inserted first can sit behind a high-priority item inserted much later. They're different ADTs with different removal rules, even though both only expose "remove one element" as an operation.

Q: Walk through implementing a queue using two stacks — why does it work?

A: Enqueues always push onto in_stack. When a dequeue is requested and out_stack is empty, pop every element off in_stack and push it onto out_stack — since a stack reverses order, the element that was pushed first onto in_stack ends up on top of out_stack, which is exactly the oldest element, the one FIFO order requires next. It works because reversing twice (once conceptually, by draining) recovers the original arrival order at the top of the second stack.

Q: What's a deque, and name a real use case for it.

A: A deque (double-ended queue) allows O(1) insertion and removal at both the front and the back, making it a strict superset of stack and queue behavior. A concrete use case is the sliding-window-maximum problem: keep a deque of indices with decreasing values, drop the front index once it falls outside the current window, and drop back indices that are smaller than a newly arriving value (they can never be the max of any window containing that new value) — the front of the deque is always the current window's maximum, computed in O(n) total.

Q: When would BFS need a queue instead of a stack, and what would happen if you used a stack by mistake?

A: BFS needs a queue because it must fully process every node at the current distance before moving on to nodes at the next distance — FIFO order guarantees that whatever was discovered earliest (and is therefore closer) gets processed first. Swapping in a stack would process the most recently discovered node next instead, which explores deep down one branch before returning to siblings — that's DFS behavior, and it breaks BFS's shortest-path-on-unweighted-graphs guarantee, usually silently rather than with an error.

Follow-up: Your two-stack queue works, but is it actually as fast as a "real" queue?

A: Amortized, yes — O(1) per operation, because each element is transferred from in_stack to out_stack exactly once over its lifetime, so the total transfer work across n operations is O(n), giving O(1) amortized per operation. But a single unlucky dequeue that triggers a full drain is O(n) in the worst case for that one call, so it's not O(1) worst-case per-call the way a circular array or linked-list queue is — worth stating explicitly if an interviewer pushes on "is this really O(1)."

Follow-up: How would you implement a queue that also supports finding the current maximum in O(1)?

A: Use a deque, not a plain queue: alongside the main FIFO storage, keep a second deque of "candidate maximums" in decreasing order — on enqueue, pop smaller values off its back before pushing the new one; on dequeue, if the removed element equals the front of the max-deque, pop that too. This is the same sliding-window-maximum technique, generalized to any enqueue/dequeue sequence rather than a fixed window.

Follow-up: Priority queues are usually built on heaps — when would you NOT use a heap for one?

A: If the priorities are small non-negative integers within a known bounded range, a bucket queue (an array of buckets indexed by priority) can give O(1) insert and O(1) find-min, beating a heap's O(log n) — this is the structure behind Dijkstra implementations with small integer edge weights (e.g. 0-1 BFS uses a deque for exactly this reason). It's a niche optimization, worth mentioning to show you know the heap isn't mandatory, just the general-purpose default.

Trade-offs

A queue is the wrong choice whenever order-of-arrival isn't actually the property you need. If importance should override arrival order — a scheduler that must run urgent jobs before older, low-priority ones — a priority queue (heap-backed) is correct and a plain queue will process things in the wrong order without any error. If you need access from both ends (recent-window statistics, a browser's forward-and-back history merged into one structure, certain dynamic-programming optimizations), a deque subsumes a plain queue's guarantees and adds flexibility for a small constant-factor cost. If you need random access to arbitrary elements by position, neither a queue nor a deque is the right primitive — reach for an array or a balanced structure instead. And for BFS-shaped problems specifically, the tell is precise: "shortest number of steps/hops on an unweighted graph" almost always wants a queue; the moment edges carry different weights, a queue's FIFO guarantee no longer implies shortest path, and you need a priority queue driving Dijkstra instead.

PracticeSolve related problems in the 150 →