λDSA Learning Hubpart of DSA Atlas

Queues

Beginner~3h · 7 lessons10 practice problems

First-in-first-out processing: deque mechanics, circular buffers, queue-with-stacks, priority-queue preview, and why BFS is a queue wearing a trench coat.

0 of 7 lessons checked off

Introduction

What it is

  • A queue admits elements at the rear and releases them from the front — First In, First Out (FIFO). enqueue, dequeue, front, rear, is_empty, size are the whole interface.
  • Cousins you'll meet immediately: the deque (both ends open), the circular queue (fixed buffer, wrapping indexes), and the priority queue (position by priority, not arrival — a heap in practice).

Why it matters

  • Queues encode fairness and order preservation: process things in the order they arrived. That is precisely what breadth-first search needs — explore all distance-k nodes before any distance-k+1 node.
  • The implementation detail interviews test: a Python list makes a BAD queue (pop(0) is O(n)); collections.deque is the O(1) tool.

How it works

  • Linked-list backing: keep head and tail pointers; enqueue at tail, dequeue at head, both O(1).
  • Array backing must avoid shifting — the circular trick: front and rear indexes advance modulo capacity, reusing freed slots.

Where it's used

  • Print spoolers, message brokers (Kafka, SQS), CPU run queues, rate limiters, and keyboard input buffers — anywhere producers and consumers run at different speeds.

In interviews

  • BFS on trees/graphs/grids (level order, shortest unweighted path), design circular queue, implement queue with stacks, sliding-window maximum (monotonic deque), recent-calls counter.
Analogy: A queue is the line at a coffee shop: you join at the back, you're served at the front, and anyone 'optimising' that order loses friends. The circular queue is the same line painted around a circular counter.

Interactive diagram

FIFO in action — arrival order is exactly service order.

An empty queue

A queue exposes both ends: items enter at the rear (enqueue) and leave from the front (dequeue). First in, first out.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Queue fundamentals and FIFO

    The contract, both ends, and the six operations.

    15 min
  2. Array-based and circular queues

    Why naive arrays fail, and how modulo indexes fix it.

    25 min
  3. Linked-list-based queue

    Head+tail pointers give O(1) at both ends.

    15 min
  4. Deque (double-ended queue)

    collections.deque: O(1) at both ends, the Swiss-army lineal structure.

    15 min
  5. Queue using stacks

    Two stacks, amortised O(1) — a favourite warm-up design question.

    20 min
  6. Priority queue (preview)

    Serve by priority instead of arrival; implemented as a heap — full topic later.

    15 min
  7. BFS use cases

    Level-order traversal and shortest paths in unweighted graphs.

    25 min

Operations

Enqueue, dequeue, front, rear

Two ends, two pointers, no traversal: every queue operation is O(1) with the right backing.

An empty queue

A queue exposes both ends: items enter at the rear (enqueue) and leave from the front (dequeue). First in, first out.

from collections import dequeclass Queue:    """FIFO queue over collections.deque. All operations O(1)."""    def __init__(self) -> None:        self._items: deque[str] = deque()    def enqueue(self, value: str) -> None:        self._items.append(value)         # rear    def dequeue(self) -> str:        if not self._items:            raise IndexError("dequeue from empty queue")        return self._items.popleft()      # front — O(1), unlike list.pop(0)    def front(self) -> str:        if not self._items:            raise IndexError("front of empty queue")        return self._items[0]    def rear(self) -> str:        return self._items[-1]    def is_empty(self) -> bool:        return not self._items    def __len__(self) -> int:        return len(self._items)
Time: O(1) per operationSpace: O(n)

Edge cases

  • dequeue/front on empty must raise.
  • One element: front and rear are the same value.
  • Interleaved enqueue/dequeue must preserve arrival order exactly.

Common mistakes

  • list.pop(0) — O(n) per dequeue, O(n²) across a BFS.
  • Using the deque's wrong end (appendleft with popleft turns it into a stack).

Circular queue on a fixed buffer

front and rear walk around a fixed array with modulo arithmetic; freed slots get reused and nothing ever shifts.

Fixed buffer of size 5

A circular queue reuses a fixed array. Two indexes — front and rear — walk around it with modulo arithmetic instead of shifting elements.

class CircularQueue:    """Fixed-capacity FIFO with wrapping indexes. O(1) ops, zero shifting."""    def __init__(self, capacity: int) -> None:        if capacity <= 0:            raise ValueError("capacity must be positive")        self._buf: list[object | None] = [None] * capacity        self._front = 0        self._size = 0    def enqueue(self, value: object) -> None:        if self.is_full():            raise OverflowError("queue is full")        rear = (self._front + self._size) % len(self._buf)        self._buf[rear] = value        self._size += 1    def dequeue(self) -> object:        if self.is_empty():            raise IndexError("dequeue from empty queue")        value = self._buf[self._front]        self._buf[self._front] = None        self._front = (self._front + 1) % len(self._buf)        self._size -= 1        return value    def is_empty(self) -> bool:        return self._size == 0    def is_full(self) -> bool:        return self._size == len(self._buf)
Time: O(1) per operationSpace: O(capacity), fixed up front

Edge cases

  • Full-vs-empty ambiguity when using only front/rear indexes — solved here by tracking size.
  • Wrap-around: rear = (front + size) % capacity.
  • Enqueue on full: raise or overwrite-oldest — a design decision to state (ring buffers overwrite).

Common mistakes

  • Computing rear without the modulo, walking off the buffer.
  • Using front == rear to mean empty AND full simultaneously without a size or a sacrificial slot.

Queue using two stacks

Pushes land in an in-box; dequeues come from an out-box, refilled by flipping the in-box when empty. Each element moves at most twice → amortised O(1).

Queue using two stacks
class QueueWithStacks:    """FIFO from two LIFOs. Amortised O(1) per operation."""    def __init__(self) -> None:        self._in: list[int] = []        self._out: list[int] = []    def enqueue(self, value: int) -> None:        self._in.append(value)    def dequeue(self) -> int:        if not self._out:                 # refill only when empty            while self._in:                self._out.append(self._in.pop())   # flip reverses order        if not self._out:            raise IndexError("dequeue from empty queue")        return self._out.pop()
Time: Amortised O(1) — each element is pushed/popped at most twiceSpace: O(n)

Edge cases

  • Dequeue with both stacks empty must raise.
  • Never flip while _out still has items — that would scramble order.
  • front() is _out[-1] if _out else _in[0].

Common mistakes

  • Flipping on every dequeue (O(n) each) instead of only when the out-box empties.
  • Flipping into the out-box while it's non-empty, interleaving generations.

Complexity analysis

OperationBestAverageWorstSpace
enqueueO(1)O(1)O(1)—
dequeue (deque/linked/circular)O(1)O(1)O(1)—
dequeue (Python list.pop(0))O(n)O(n)O(n)—
front / rear / is_emptyO(1)O(1)O(1)—
searchO(1)O(n)O(n)O(1)

One row is a trap on purpose: the list-backed dequeue. Quoting O(1) queue costs while using list.pop(0) is a classic interview own-goal.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Linked-list queue with head and tail pointers
from typing import Optionalclass _Node:    __slots__ = ("value", "next")    def __init__(self, value: object):        self.value = value        self.next: Optional["_Node"] = Noneclass LinkedQueue:    """FIFO queue: dequeue at head, enqueue at tail. O(1) worst case."""    def __init__(self) -> None:        self._head: Optional[_Node] = None    # front        self._tail: Optional[_Node] = None    # rear        self._size = 0

What interviewers expect you to know

What interviewers expect you to know

  • FIFO contract and why BFS requires it: the queue IS the level-order guarantee.
  • list.pop(0) is O(n); collections.deque.popleft() is O(1) — say it before they ask.
  • Circular queue mechanics: modulo indexes, the full/empty ambiguity, and one resolution (size counter or sacrificial slot).
  • Deque vs queue vs priority queue: both-ends vs one-way vs by-priority.

Classic follow-ups

  • "Implement a stack using queues" — the mirror exercise: rotate the queue after each push (O(n) push, O(1) pop).
  • "Why is your queue-with-stacks O(1) if the flip is O(n)?" — amortised: each element crosses at most twice; charge the flip to the elements moved.
  • "Sliding-window maximum?" — a monotonic deque: front holds the max, back evicts dominated values. Bridges to the monotonic pattern page.

How to explain a queue solution

  • For BFS, narrate the invariant: 'everything in the queue is at distance d or d+1, in order' — that sentence is the proof of shortest paths.
  • Name the backing structure and its costs when you write it: 'deque, so both ends are O(1).'

Common mistakes

list as a queue

pop(0) shifts every element: an innocent-looking BFS becomes O(V²). deque.popleft() exists for exactly this.

Marking visited at dequeue time

In BFS, mark nodes visited when ENQUEUED. Marking at dequeue lets the same node enter the queue many times — exponential blowup on dense graphs.

Circular full/empty confusion

front == rear is ambiguous. Track size explicitly or keep one slot empty; say which convention you chose.

Tail pointer left dangling

Dequeuing the last node must also null the tail; forgetting it makes the next enqueue append to a ghost node.

Flipping stacks too eagerly

In queue-with-stacks, flip only when the out-box is empty. Early flips both break order and destroy the amortised bound.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (1)

Medium (7)

Hard (2)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. What does this print?
    from collections import dequeq = deque()q.append(1); q.append(2); q.append(3)q.popleft()q.append(4)print(q[0], q[-1])
  2. Complexity2. A BFS dequeues with list.pop(0) over V vertices. Total dequeue cost?
  3. Concept3. In a circular queue with capacity 5, front = 3 and size = 4. Where does the next enqueue land?
  4. Scenario4. Why does BFS — not DFS — find shortest paths in an unweighted graph?
  5. Concept5. Queue-with-two-stacks: dequeue is amortised O(1) because…
0 of 5 answered

Frequently asked questions

When do I need a deque instead of a queue?

When both ends are active: sliding-window maximum (evict from the back, read from the front), palindrome checks, work-stealing schedulers. If only rear-in/front-out happen, a queue interface keeps intent clearer.

What is a priority queue relative to this page?

A queue where dequeue returns the highest-priority item, not the oldest. It's implemented with a binary heap — covered fully on the Heaps page. Interview shorthand: 'queue' = FIFO, 'priority queue' = heap.

Is a circular queue still relevant with dynamic arrays around?

Yes — fixed memory plus O(1) ops make ring buffers the standard in embedded systems, audio pipelines, and network cards, and 'Design Circular Queue' remains a common interview design question.

Summary & cheat sheet

Key takeaways

  • Queue = FIFO; deque.popleft(), never list.pop(0).
  • Circular queue: modulo indexes over a fixed buffer; resolve full-vs-empty explicitly.
  • Queue-with-stacks: flip lazily; amortised O(1).
  • BFS is queue-order made algorithmic: first arrival = shortest unweighted path.
  • Mark visited on enqueue, not dequeue.

Formulas & cheat sheet

  • rear index = (front + size) % capacity
  • Items in a circular buffer: (rear − front + capacity) % capacity (when tracking indexes only)
  • Amortised bound: total element moves ≤ 2n over n operations

Interview checklist

  • I can implement a circular queue with a size counter.
  • I can write BFS with a deque and enqueue-time visited marking.
  • I can implement a queue from two stacks and defend its amortised cost.
  • I know when a deque or priority queue is the actual requirement.