06Module · Goodrich Ch. 6

Week 6 — Stacks, Queues & Deques

ADTs and array-based implementations; applications: expression matching, schedulers, data reversal.

Stacks, Queues & Deques

LIFO/FIFO/double-ended abstractions and their array-backed implementations.

Theory

A stack provides LIFO access via push/pop/top in O(1) — the engine behind function calls, undo, and DFS.

A queue provides FIFO access via enqueue/dequeue in O(1) using a circular array to avoid shifting.

A deque supports O(1) insertion and removal at both ends — Python's collections.deque is the canonical implementation.

Key points

Use a stack to match opening/closing brackets in expressions.
Circular array: index = (front + i) % capacity.
list.pop(0) is O(n); use deque.popleft() for O(1).

Code examples

Balanced parentheses

def is_matched(expr):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in expr:
        if c in "([{":
            stack.append(c)
        elif c in ")]}":
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

Array-based circular queue

class ArrayQueue:
    DEFAULT_CAP = 10
    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAP
        self._size = 0
        self._front = 0

    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front + self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("empty")
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer

    def _resize(self, cap):
        old = self._data
        self._data = [None] * cap
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1 + walk) % len(old)
        self._front = 0