Queues & Circular Buffers
You'll learn to
- -Explain the FIFO (first-in, first-out) principle behind a queue
- -Understand why a naive list-based queue is O(n) per dequeue
- -Implement a circular buffer that achieves O(1) enqueue and dequeue
A queue mirrors the stack from the last chapter but flips the rule entirely: first in, first out (FIFO) instead of last in, first out. That single change represents a completely different family of real-world problems - anything where fairness or arrival order matters more than recency.
FIFO: First In, First Out
A checkout line, a printer's job queue, and a support ticket system all follow the same pattern - whoever arrived first gets served first. In software, this shows up constantly: task scheduling (jobs processed in the order they were submitted), breadth-first search (a later-tier preview), rate limiters (tracking a recent window of request timestamps), and message-queue-driven pipelines like the asynchronous systems covered in the HLD course.
The Naive Approach, and Why pop(0) Is O(n)
A Python list is a contiguous array under the hood. Appending at the end is O(1) because there is free capacity waiting there, but removing from the front with pop(0) (or inserting at the front with insert(0, x)) forces every other element to shift one slot to close the resulting gap - a full O(n) pass. That turns an operation that looks trivial into a real bottleneck: a queue built this way pays O(n) on every single dequeue, no matter how the queue is used.
The Fix: A Circular Buffer
A circular buffer (or ring buffer) fixes this by using a fixed-size array along with two index counters - head, marking the next item to remove, and tail, marking the next free slot to fill - plus a running count of how many items are currently stored. When tail (or head) reaches the end of the array, it simply wraps back around to index 0 instead of running off the end, which is exactly where the name "circular" comes from. Because both enqueue and dequeue only ever touch head and tail, and never shift any other element, both are genuinely O(1).
Walking through it concretely: with capacity 4, enqueuing four values fills indices 0 through 3 and leaves tail wrapped back to 0. Dequeuing two frees indices 0 and 1 (head moves to index 2). Enqueuing two more values writes directly into those freed slots at indices 0 and 1 - the modulo arithmetic wraps tail back around automatically, so the array never needs to grow or shift a single existing element.
A fixed-capacity circular buffer should raise once full, exactly as written above. A production queue that needs unbounded growth instead resizes the underlying buffer (a copy-and-grow step, the same idea behind a dynamic array) or blocks and rejects new items - Level 3 specifically asks for the fixed-capacity version shown here.
Level 3: Queue from Scratch asks you to implement exactly this - a Queue class using a circular buffer with fixed capacity, giving true O(1) enqueue and dequeue instead of the O(n) list.pop(0) approach shown above.