05. Stacks and Queues

Stacks and queues are restricted data structures. They limit how you access elements — and that restriction is the point. By constraining access to one end (stack) or two ends (queue), you get structures that model real problems naturally: undo history, function calls, task scheduling, breadth-first search.

Stacks — Last In, First Out

A stack lets you push to the top and pop from the top. The last thing you added is the first thing you remove. Think of a stack of plates.

In Python, a regular list is a stack:

stack = []

stack.append(1)  # push
stack.append(2)  # push
stack.append(3)  # push

top = stack[-1]   # peek — 3
stack.pop()       # pop — removes and returns 3

append() and pop() are both amortized O(1). No need for a special class — a list with append/pop is a stack. Never use pop(0) for a stack — that's O(n).

Where Stacks Appear

Function call stack — every function call pushes a frame, every return pops it. Recursion is just the call stack doing the work for you.

Undo/redo — each action pushes to the undo stack. Undo pops and pushes to redo.

Expression evaluation — parsing (3 + (4 * 2)) uses a stack to match parentheses and track operator precedence.

LeetCode 20 - Valid Parentheses

def is_valid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

Monotonic Stack

A stack where elements are always in sorted order (increasing or decreasing). Used to find the "next greater element" or "previous smaller element" in O(n).

The pattern (used by LeetCode 496, 503, 739, 84):

def next_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n   # default: no greater element found
    stack = []           # indices of elements still waiting for their "next greater"

    for i in range(n):
        # Current element is greater than what's on top of stack?
        # Then current IS the "next greater" for those waiting elements
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()        # this element found its answer
            result[idx] = nums[i]    # record it
        stack.append(i)  # current element now waits for its own next greater
    return result

# Example: nums = [2, 1, 3]
# i=0: stack=[], push 0 → stack=[0]
# i=1: nums[1]=1 < nums[0]=2, push 1 → stack=[0,1]
# i=2: nums[2]=3 > nums[1]=1 → pop 1, result[1]=3
#      nums[2]=3 > nums[0]=2 → pop 0, result[0]=3
#      push 2 → stack=[2]
# Result: [3, 3, -1]

Without a monotonic stack, this is O(n²) — for each element, scan right to find the next greater. The stack makes it O(n) because each element is pushed and popped at most once.

LeetCode 739 - Daily Temperatures

Given daily temperatures, return how many days you have to wait for a warmer day. If no warmer day exists, return 0. Example: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices of days waiting for a warmer day

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)
    return result

Queues — First In, First Out

A queue lets you add to the back and remove from the front. First thing in is the first thing out. Think of a line at a store.

Don't use a list as a queue. list.pop(0) is O(n) because it shifts every element. Use collections.deque:

from collections import deque

queue = deque()

queue.append(1)     # enqueue (right end)
queue.append(2)     # enqueue
queue.append(3)     # enqueue

front = queue[0]    # peek — 1
queue.popleft()     # dequeue — removes and returns 1

deque is implemented as a doubly-linked list of fixed-size blocks. Both append() and popleft() are O(1) — no shifting, no memory leak.

Why Not list.pop(0)?

# BAD — O(n) dequeue
queue = [1, 2, 3, 4, 5]
queue.pop(0)  # shifts elements 2,3,4,5 one position left

# GOOD — O(1) dequeue
from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.popleft()  # O(1), no shifting

For BFS on a graph with 100,000 nodes, using list.pop(0) turns O(n) BFS into O(n²). Always use deque.

Where Queues Appear

BFS (Breadth-First Search) — the most important use. Process nodes level by level.

from collections import deque

def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Task scheduling — process jobs in the order they arrive.

Rate limiting — sliding window of timestamps.

Deque — Double-Ended Queue

collections.deque supports O(1) operations at both ends. This makes it perfect for sliding window problems where you need to remove from both the front and back.

LeetCode 239 - Sliding Window Maximum

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()  # stores indices, front is always the max
    result = []

    for i in range(len(nums)):
        # Remove elements outside the window
        while dq and dq[0] <= i - k:
            dq.popleft()
        # Remove smaller elements from back (they'll never be the max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Python's queue Module

Python also has queue.Queue (thread-safe) and queue.LifoQueue (thread-safe stack). These are for multi-threaded programs — they use locks internally. For single-threaded code and interviews, use list (stack) and deque (queue).

# Only use these for threading
from queue import Queue, LifoQueue

q = Queue()
q.put(1)
q.get()  # blocks if empty

Operation Costs

When to Use Stack vs Queue

Stack when:

• You need to reverse order or backtrack
• Matching pairs (parentheses, HTML tags)
• DFS traversal (iterative)
• Monotonic problems (next greater/smaller)

Queue when:

• You need to process in arrival order
• BFS traversal
• Level-order processing
• Scheduling and buffering

Deque when:

• You need both stack and queue behavior
• Sliding window problems
• You need O(1) access to both ends

Practice Problems

Key Takeaways

• Stacks are LIFO — use a list with append()/pop() in Python
• Queues are FIFO — always use collections.deque, never list.pop(0)
• Monotonic stacks solve "next greater/smaller" problems in O(n) instead of O(n²)
• deque gives O(1) operations at both ends — used for sliding window maximum
• The restriction IS the feature — limiting access makes the structure match the problem
• BFS always uses a queue; DFS always uses a stack (or recursion, which is an implicit stack)