Stacks & Queues

Stacks & Queues

Stack — Last In, First Out (LIFO). Push/pop from the same end. Queue — First In, First Out (FIFO). Enqueue one end, dequeue the other.

The Call Stack

Every recursive function call uses the call stack implicitly:

• Each call pushes the current function state (local variables, return address)
• When the function returns, it pops that frame
• Deep or infinite recursion → stack overflow
• This is why iterative solutions with explicit stacks can be more memory-safe

BFS Uses a Queue

In BFS, when you visit a node you add all its unvisited neighbours to the end of the queue. This guarantees level-by-level exploration:

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for neighbour in graph.get(node, []):
            if neighbour not in visited:
                visited.add(neighbour)
                q.append(neighbour)

Python Built-ins

# Stack — use list
stack = []
stack.append(x)   # push  O(1)
stack.pop()       # pop   O(1)
stack[-1]         # peek  O(1)

# Queue — ALWAYS use deque (list.pop(0) is O(n)!)
from collections import deque
q = deque()
q.append(x)       # enqueue  O(1)
q.popleft()       # dequeue  O(1)
q[0]              # peek     O(1)

Complexity

| Operation | Stack | Queue (deque) | |-----------|-------|-------| | Push/Enqueue | O(1) | O(1) | | Pop/Dequeue | O(1) | O(1) | | Peek | O(1) | O(1) | | Search | O(n) | O(n) |

Min Stack — O(1) min()

Maintain a parallel min stack that tracks the current minimum at every level:

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []   # top = current minimum

    def push(self, val):
        self.stack.append(val)
        # Push new min: either val or keep existing min
        current_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(current_min)

    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()

    def min(self):
        return self.min_stack[-1]

The key insight: when pushing, push min(val, current_min) — not just val. When popping, always pop both stacks together.

Balanced Parentheses

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        elif c in ')]}':
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
    return len(stack) == 0

Sort a Stack (using 1 extra stack)

def sort_stack(s):
    temp = []
    while s:
        val = s.pop()
        # Move values back from temp that are smaller than val
        while temp and temp[-1] < val:
            s.append(temp.pop())
        temp.append(val)
    return temp  # sorted, smallest on top

Time: O(n²), Space: O(n).

Multiple Stacks in One Array

Divide a single array into N equal segments — each segment is a stack:

• Track a top[i] pointer for each stack
• Handle overflow by resizing the segment or throwing an error
• More complex variant: allow segments to grow dynamically using a linked list of "stack frames"

Key Interview Tips

• Stack → DFS, expression evaluation, function call simulation, monotonic problems
• Queue → BFS, task scheduling, sliding window maximum
• Monotonic stack: keeps elements in monotonic order — powerful for "next greater element"
• Two stacks can simulate a queue (and vice versa) — classic interview question
• deque supports O(1) at both ends — use it instead of list for queues