Stacks, Queues, and Deques

Updated

October 31, 2026

Stacks, Queues, and Deques

A stack is a Last-In, First-Out (LIFO) structure used for back-tracking, undo operations, and expression parsing. A queue is a First-In, First-Out (FIFO) structure used for job scheduling and stream buffering. A deque (double-ended queue) supports constant-time additions and removals at both ends. In Python, the boring default for a stack is a standard list, while the mandatory default for a queue is collections.deque.

Stack and Queue Data Structure Diagram

Mental model

In a stack, push and pop occur at the tail of the list:

Stack (LIFO - Python list):
Push: items.append(x)  -> [ #101, #102, #103 ] <- Pop: items.pop()
                                          ^ Top

In a queue, items enter at one end and leave from the other. If you implement a queue with a standard Python list, calling items.pop(0) requires Python to shift every remaining pointer one slot to the left, which costs \(O(n)\) time. For 100,000 items, that is 10 billion operations.

collections.deque is implemented internally as a doubly-linked block of contiguous arrays. Both append() and popleft() run in guaranteed \(O(1)\) time regardless of queue length:

Deque (FIFO - collections.deque):
Enqueue (append) --------> [ Block 1 ] <---> [ Block 2 ] --------> Dequeue (popleft)

Worked examples

Case 1: LIFO Stack for Expression and Delimiter Validation

Save as stack_validator.py. Validate whether desk billing expressions and nested brackets are properly balanced.

# stack_validator.py
class Stack[T]:
    def __init__(self) -> None:
        self._items: list[T] = []

    def push(self, val: T) -> None:
        self._items.append(val)

    def pop(self) -> T | None:
        return self._items.pop() if self._items else None

    def peek(self) -> T | None:
        return self._items[-1] if self._items else None

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def __len__(self) -> int:
        return len(self._items)


def is_balanced(expression: str) -> bool:
    pairs = {")": "(", "}": "{", "]": "["}
    openers = set(pairs.values())
    stack: Stack[str] = Stack()

    for ch in expression:
        if ch in openers:
            stack.push(ch)
        elif ch in pairs:
            top = stack.pop()
            if top != pairs[ch]:
                return False

    return stack.is_empty()


def main() -> None:
    formula1 = "ORDER_TOTAL([ITEM(101) + TAX{0.08}] * QTY(2))"
    formula2 = "ORDER_TOTAL([ITEM(101) + TAX{0.08)]"  # Mismatched ] with }

    print(f"Formula 1 valid: {is_balanced(formula1)}")
    print(f"Formula 2 valid: {is_balanced(formula2)}")


if __name__ == "__main__":
    main()

Run:

uv run python stack_validator.py

Output:

Formula 1 valid: True
Formula 2 valid: False

Case 2: High-Performance FIFO Queue with collections.deque

Save as queue_dispatch.py. Dispatch customer support and kitchen orders in first-come, first-served order.

# queue_dispatch.py
from collections import deque
from dataclasses import dataclass


@dataclass(slots=True)
class Order:
    id: int
    table: int
    item: str


class OrderQueue:
    def __init__(self) -> None:
        self._queue: deque[Order] = deque()

    def enqueue(self, order: Order) -> None:
        self._queue.append(order)

    def dequeue(self) -> Order | None:
        if not self._queue:
            return None
        return self._queue.popleft()  # True O(1) removal

    def __len__(self) -> int:
        return len(self._queue)


def main() -> None:
    q = OrderQueue()
    q.enqueue(Order(id=101, table=3, item="Cappuccino"))
    q.enqueue(Order(id=102, table=1, item="Croissant"))
    q.enqueue(Order(id=103, table=5, item="Green Tea"))

    print(f"Total pending orders: {len(q)}")

    while len(q) > 0:
        order = q.dequeue()
        assert order is not None
        print(f"Serving Order #{order.id} for Table {order.table}: {order.item}")


if __name__ == "__main__":
    main()

Run:

uv run python queue_dispatch.py

Output:

Total pending orders: 3
Serving Order #101 for Table 3: Cappuccino
Serving Order #102 for Table 1: Croissant
Serving Order #103 for Table 5: Green Tea

Case 3: Fixed-size Ring Buffer (Circular Buffer)

Save as ring_buffer.py. Implement a circular buffer with a fixed memory footprint that tracks the last \(N\) audit logs, automatically overwriting the oldest entries.

# ring_buffer.py
class RingBuffer[T]:
    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("Capacity must be positive")
        self._cap = capacity
        self._buf: list[T | None] = [None] * capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def append(self, item: T) -> None:
        self._buf[self._tail] = item
        self._tail = (self._tail + 1) % self._cap
        if self._size < self._cap:
            self._size += 1
        else:
            # Overwriting oldest element -> advance head
            self._head = (self._head + 1) % self._cap

    def to_list(self) -> list[T]:
        items: list[T] = []
        for i in range(self._size):
            idx = (self._head + i) % self._cap
            val = self._buf[idx]
            if val is not None:
                items.append(val)
        return items


def main() -> None:
    # Retain only the last 3 audit messages
    audit_log: RingBuffer[str] = RingBuffer(3)

    audit_log.append("10:01 User logged in")
    audit_log.append("10:02 Ticket #44 created")
    audit_log.append("10:05 Ticket #44 assigned")
    print("Initial log buffer:", audit_log.to_list())

    print("Adding 4th message (overwrites oldest)...")
    audit_log.append("10:08 Ticket #44 closed")
    print("Updated log buffer:", audit_log.to_list())


if __name__ == "__main__":
    main()

Run:

uv run python ring_buffer.py

Output:

Initial log buffer: ['10:01 User logged in', '10:02 Ticket #44 created', '10:05 Ticket #44 assigned']
Adding 4th message (overwrites oldest)...
Updated log buffer: ['10:02 Ticket #44 created', '10:05 Ticket #44 assigned', '10:08 Ticket #44 closed']

The trap

The most common trap in Python is using my_list.pop(0) for a FIFO queue. It works without error during testing when \(n = 5\), but turns into an invisible \(O(n^2)\) freeze when processing real workloads with 50,000 items. Always use collections.deque with popleft().

The boring rule

  1. Use standard list with .append() and .pop() for LIFO stacks.
  2. Use collections.deque with .append() and .popleft() for FIFO queues.
  3. If you only need a rolling window of the last \(N\) items, pass maxlen=N to collections.deque(maxlen=N), which implements a C-level ring buffer automatically.
  4. Do not hand-roll a queue using custom linked list nodes in Python unless learning; collections.deque is heavily optimized in C.

Try this

  1. Use collections.deque(maxlen=5) to track the 5 most recent search queries entered by a user.
  2. Build an UndoRedoManager using two stacks (undo_stack and redo_stack) to support reversible desk ticket edits.