Chapter 3: Stacks, Queues, and Deques

Vol 2: Algorithm Forest Adventure · Station 3

---

Metadata Card

Attribute	Value
Chapter	Vol 2 · Chapter 3
Difficulty	(Beginner Reinforcement)
Prerequisites	Arrays, Linked Lists (Chapter 2)
Core Skills	LIFO / FIFO, circular indexing, monotonic thinking
Keywords	Stack Queue Deque Circular Buffer Monotonic Stack Monotonic Queue

---

Your Progress

After crossing the two forks, you find that forest resources need to be queued for use. You must process the most recently acquired map before looking at earlier ones (stack). On the other side, resources arrive in order and depart in order (queue).

A wooden sign reads: three containers — Last-In-First-Out, First-In-First-Out, Both Ends Open.

---

Breakthrough · Origins

Encounter #1: Stack (LIFO)

class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

Application: Bracket Matching

def is_valid_brackets(s: str) -> bool:
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '({[':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pair[ch]:
                return False
    return not stack

Encounter #2: Queue (FIFO)

class CircularQueue:
    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, item):
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._data[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._data[self._head]
        self._data[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value

    def is_empty(self):
        return self._size == 0

    def _resize(self, new_cap):
        old = self._data
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[(self._head + i) % self._capacity]
        self._head = 0
        self._tail = self._size
        self._capacity = new_cap

Encounter #3: Deque

from collections import deque

dq = deque()
dq.append("right")       # push right
dq.appendleft("left")    # push left
print(dq.pop())          # pop right → "right"
print(dq.popleft())      # pop left → "left"

Application: BFS Level-Order Traversal

def bfs_level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

---

Common Pitfalls

1. Don't use list.pop(0) for queues — O(n), not O(1). Use collections.deque.
2. Forgetting the modulus (%) in circular queues — head/tail will go out of bounds.
3. Stack overflow in recursion — Python's recursion limit is ~1000. Use an explicit stack for deep traversals.

---

Verification Checklist

• [ ] Can hand-write stack with push/pop/peek
• [ ] Can hand-write circular queue with enqueue/dequeue
• [ ] Can explain why collections.deque is O(1) on both ends
• [ ] Can implement bracket matching or BFS with these structures

---

Traveler's Notes

1. Stack — LIFO. Array implementation is simplest.
2. Queue — FIFO. Circular array is the proper implementation.
3. Deque — Python's Swiss Army knife, both ends O(1).
4. Bracket matching — compilers use this every day.
5. BFS — without a queue, no elegant level-by-level expansion.

---

→ Next Stop Preview

Chapter 4: Hash Tables — "O(1) lookup — magic or math?"