03 — Stacks, Queues, Deques & Bounded Ring Buffers

At a glance

After completing this lesson you can:

• Distinguish LIFO (Stack) and FIFO (Queue) access patterns and implement them with $O(1)$ operations.
• Leverage collections.deque and monotonic stacks/queues to solve backend buffering and sliding window problems.
• Build a production-grade circular ring buffer to manage backpressure without memory leaks.

Time: ~50 minutes · Prerequisites: 02 — Hash Tables & Sets

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 3: Recursion (The Call Stack, Stacks in computation).
• Book: Fluent Python (2nd Edition) — Luciano Ramalho
• Chapter 2: Deques and Other Sequences (Using collections.deque for FIFO queues).

Why this matters in production

When an upstream source fires events faster than your database or workers can process them, an unbounded queue (list or asyncio.Queue()) will quietly consume RAM until the host crashes from an OOM kill. A bounded ring buffer or bounded queue establishes backpressure: it rejects excess requests, sheds non-critical load, or pauses upstream producers safely.

Deep dive

1. Stack (LIFO) vs Queue (FIFO)

• Stack (Last In, First Out): Call stack, undo history, DFS traversal, balanced parentheses/tags. Python's list works fine as a stack using append() and pop().
• Queue (First In, First Out): Job queues, rate limit windows, BFS traversal. Using list.pop(0) is $O(n)$! Always use collections.deque which provides $O(1)$ popleft().

2. The Circular Ring Buffer

A ring buffer uses a fixed-size array and two pointer indices: head (write position) and tail (read position), wrapping around using modulo arithmetic: next_pos = (pos + 1) % capacity.

Circular Buffer (Capacity 4):
[ A, B, C, D ]
  ^        ^
 tail     head   (full)
After 1 read: tail moves to index 1.

Hands on

python3 phase1-cs-and-architecture/01-data-structures/03-stacks-queues-and-deques/examples/01_demo.py
python3 phase1-cs-and-architecture/01-data-structures/03-stacks-queues-and-deques/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — O(N) QUEUE VIA LIST.POP(0)
class MessageQueue:
    def __init__(self):
        self.queue = []
    def enqueue(self, msg):
        self.queue.append(msg)
    def dequeue(self):
        return self.queue.pop(0)  # O(n) array shift on EVERY message!

Exercises

1. Rung 1 (validate_balanced_delimiters): Use a stack to check matching brackets/tags ((), [], {}) in a code string.
2. Rung 2 (drain_queue_batch — Fix the AI Bug): Fix an $O(n^2)$ queue drain that uses list.pop(0) by refactoring to collections.deque.
3. Rung 3 (CircularRingBuffer): Implement a circular ring buffer with fixed capacity using an internal list and modulo pointers.
4. Rung 4 (MonotonicMaxQueue): Build a queue supporting push, pop, and get_max() in $O(1)$ amortized time using a monotonic deque.
5. Rung 5 (BackpressureChannel): Build a bounded producer-consumer channel supporting drop-oldest and drop-newest overflow policies.

Wrapping up

Can you explain?

1. Why is collections.deque.popleft() $O(1)$ while list.pop(0) is $O(n)$?
2. What is a monotonic stack and why is it useful for sliding window maximums?
3. How does modulo arithmetic prevent memory allocation in a ring buffer?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series