Stacks & Queues: Simple to Learn, Sneaky to Master

The Confidence Trap

Stacks and queues are the first data structures most programmers learn. Push, pop, enqueue, dequeue — the operations are so simple that candidates often underestimate them entirely.

That's the trap.

In interviews, stacks and queues don't appear as straightforward "implement a stack" questions. They appear as problems where the optimal solution happens to use a stack or queue — and candidates who don't recognize that pattern reach for nested loops, brute force, or increasingly complicated logic while the O(n) solution using a monotonic stack or deque sits right there, invisible to anyone who wrote off these structures as "too basic to study."

This post covers everything: how stacks and queues work under the hood, the implementation patterns you need to know, and — most importantly — the advanced patterns that make these structures the secret weapon behind some of the most elegant O(n) solutions in the entire interview problem space.

Stack: Last In, First Out

A stack operates on one end. The last element pushed is the first one popped — like a stack of plates.

# Python: use a list as a stack
stack = []
stack.append(3)    # push: O(1) amortized
stack.append(7)
stack.append(1)

top = stack[-1]    # peek: O(1), does NOT remove
val = stack.pop()  # pop: O(1) amortized, removes and returns top
empty = not stack  # check empty: O(1)

When to think "stack": Problems involving nested structure, matching pairs, "undo" semantics, or anything where you need to process the most recently seen thing first.

LIFO mental model:
  Push 3 → [3]
  Push 7 → [3, 7]
  Push 1 → [3, 7, 1]
  Pop   → returns 1, stack is [3, 7]
  Peek  → returns 7, stack unchanged

Queue: First In, First Out

A queue operates on two ends. The first element enqueued is the first one dequeued — like a line at a coffee shop.

from collections import deque

# Python: ALWAYS use deque for queues, never list
queue = deque()
queue.append(3)      # enqueue: O(1)
queue.append(7)
queue.append(1)

front = queue[0]     # peek front: O(1)
val = queue.popleft() # dequeue: O(1)  ← this is why deque, not list
empty = not queue

Why not list for queues? list.pop(0) is O(n) — it shifts every remaining element. deque.popleft() is O(1). In interview code, using list.pop(0) in a BFS loop turns your O(n) algorithm into O(n²). Always use deque.

Pattern 1: Valid Parentheses and Matching Pairs

The classic stack interview problem. Whenever you see an opening bracket, push it. Whenever you see a closing bracket, check if it matches the top of the stack.

def is_valid(s):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.append(char)          # push opening bracket
        elif char in ')}]':
            if not stack or stack[-1] != matching[char]:
                return False            # no match
            stack.pop()                 # matched — remove

    return not stack                    # valid only if nothing left unmatched

The extension — longer matching problems:

def remove_invalid_parentheses_count(s):
    """Count minimum removals to make parentheses valid."""
    open_count = 0
    close_count = 0

    for char in s:
        if char == '(':
            open_count += 1
        elif char == ')':
            if open_count > 0:
                open_count -= 1    # matched an open
            else:
                close_count += 1   # unmatched close

    return open_count + close_count

def min_add_to_make_valid(s):
    """Minimum additions to make parentheses valid."""
    open_needed = 0    # closing brackets needed
    close_needed = 0   # opening brackets needed

    for char in s:
        if char == '(':
            open_needed += 1
        else:
            if open_needed > 0:
                open_needed -= 1
            else:
                close_needed += 1

    return open_needed + close_needed

Canonical Problems

• Valid Parentheses (Easy)

• Minimum Add to Make Parentheses Valid (Medium)

• Longest Valid Parentheses (Hard)

Pattern 2: Stack for Expression Evaluation

Stacks are the natural structure for evaluating expressions — both arithmetic and postfix (Reverse Polish Notation).

def eval_rpn(tokens):
    """Evaluate Reverse Polish Notation expression."""
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),   # truncate toward zero
    }

    for token in tokens:
        if token in ops:
            b = stack.pop()    # second operand (popped first)
            a = stack.pop()    # first operand
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))

    return stack[0]

def calculate_basic(s):
    """Calculate string expression with +, -, and parentheses."""
    stack = []
    result = 0
    num = 0
    sign = 1    # +1 for positive, -1 for negative

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char == '+':
            result += sign * num
            num = 0
            sign = 1
        elif char == '-':
            result += sign * num
            num = 0
            sign = -1
        elif char == '(':
            stack.append(result)    # save current result
            stack.append(sign)      # save current sign
            result = 0
            sign = 1
        elif char == ')':
            result += sign * num
            num = 0
            result *= stack.pop()   # apply sign before parenthesis
            result += stack.pop()   # add result before parenthesis

    return result + sign * num

Canonical Problems

• Evaluate Reverse Polish Notation (Medium)

• Basic Calculator (Hard)

• Basic Calculator II (Medium)

Pattern 3: Monotonic Stack

This is the pattern most candidates don't have. It's behind some of the most elegant O(n) solutions in the problem space — and it appears in more interview problems than most people realize.

The Core Idea

A monotonic stack maintains elements in a strictly increasing or decreasing order. When a new element violates the ordering, you pop elements off and process them — usually computing some value that relates the popped element to the current one.

The key insight: each element is pushed once and popped once, so the total work across the entire algorithm is O(n), regardless of how many pops happen at each step.

Next Greater Element

def next_greater_element(nums):
    """For each element, find the next greater element to its right."""
    result = [-1] * len(nums)
    stack = []    # stores indices, not values

    for i, num in enumerate(nums):
        # Pop elements smaller than current — current is their "next greater"
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num    # nums[i] is the next greater for nums[idx]
        stack.append(i)

    # Elements remaining in stack have no next greater → result stays -1
    return result

# nums = [2, 1, 5, 3, 6]
# result = [5, 5, 6, 6, -1]

Step through this once manually until the popping logic is automatic.

Daily Temperatures

The exact same pattern — "how many days until a warmer temperature?":

def daily_temperatures(temps):
    result = [0] * len(temps)
    stack = []    # indices of temperatures waiting for a warmer day

    for i, temp in enumerate(temps):
        while stack and temps[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx    # days until warmer
        stack.append(i)

    return result

Largest Rectangle in Histogram

The hardest canonical monotonic stack problem:

def largest_rectangle_histogram(heights):
    """Find the largest rectangle that fits under the histogram bars."""
    stack = []    # indices, heights are non-decreasing in stack
    max_area = 0
    # Append 0 as sentinel — forces all bars to be processed
    heights = heights + [0]

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # Width: from current position back to the new stack top
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Why it works: The stack maintains bar indices in non-decreasing height order. When a shorter bar arrives, every taller bar that gets popped can no longer extend to the right — its right boundary is the current bar. Its left boundary is the new stack top. This gives the maximum rectangle for that height in O(1) per bar.

Trapping Rain Water

Another classic that collapses to O(n) with the right approach:

def trap(height):
    """Calculate total water trapped between bars."""
    # Two-pointer approach — O(n) time, O(1) space
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

Canonical Problems

• Daily Temperatures (Medium)

• Next Greater Element I (Easy)

• Largest Rectangle in Histogram (Hard)

• Trapping Rain Water (Hard)

Pattern 4: Queue for BFS

The queue is the engine behind Breadth-First Search. Every BFS — on trees, graphs, or grids — follows the same template.

from collections import deque

def bfs_template(start, graph):
    visited = {start}
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)          # process current node

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

    return result

# BFS on a grid (flood fill, number of islands, shortest path)
def bfs_grid(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    visited = {(start_r, start_c)}
    queue = deque([(start_r, start_c, 0)])    # (row, col, distance)
    directions = [(0,1),(0,-1),(1,0),(-1,0)]

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and (nr, nc) not in visited
                    and grid[nr][nc] != '#'):    # not a wall
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

Level-by-level BFS — when you need to track which level each node is on:

def bfs_level_by_level(root):
    if not root:
        return []
    queue = deque([root])
    result = []

    while queue:
        level_size = len(queue)    # snapshot: all nodes at current level
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(current_level)

    return result

The level_size = len(queue) snapshot is the critical line. It captures exactly how many nodes are at the current level before you start adding the next level's nodes.

Canonical Problems

• Binary Tree Level Order Traversal (Medium)

• Rotting Oranges (Medium)

• Word Ladder (Hard)

Pattern 5: Deque for Sliding Window Maximum

The deque (double-ended queue) supports O(1) operations on both ends. This unlocks the sliding window maximum — a problem that seems to require O(k) per window step but can be solved in O(n) total.

from collections import deque

def max_sliding_window(nums, k):
    """Maximum value in each sliding window of size k. O(n) total."""
    result = []
    dq = deque()    # stores indices; values are decreasing (monotonic deque)

    for i, num in enumerate(nums):
        # Remove indices outside the current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements — they can never be the maximum
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # Start adding results once first window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])    # front of deque is always the max

    return result

Why O(n)? Each index is added to and removed from the deque exactly once. Total operations: 2n = O(n).

The monotonic deque invariant: Elements in the deque are always in decreasing order of value. When we add a new element, we remove all smaller elements from the back first — they can never be the maximum for any future window, because the new element is both larger and more recent (will leave the window later).

# Sliding window minimum — flip the comparison
def min_sliding_window(nums, k):
    result = []
    dq = deque()    # stores indices; values are increasing

    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] > num:    # flip: remove larger elements
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Canonical Problems

• Sliding Window Maximum (Hard)

• Shortest Subarray with Sum at Least K (Hard)

Pattern 6: Stack to Simulate Recursion / Implement Queue

Two classic "implement X using Y" problems that appear regularly:

Min Stack — O(1) Minimum at All Times

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []    # parallel stack tracking minimums

    def push(self, val):
        self.stack.append(val)
        # Push new min: either val is smaller, or current min stays
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_val)

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

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]    # O(1) — always current min

The insight: The min_stack tracks "what is the minimum of all elements at or below this position?" When you pop from the main stack, you pop from min_stack too — maintaining the invariant.

Implement Queue Using Two Stacks

class MyQueue:
    def __init__(self):
        self.inbox = []     # new elements pushed here
        self.outbox = []    # elements dequeued from here

    def push(self, val):
        self.inbox.append(val)    # O(1)

    def pop(self):
        self._transfer()
        return self.outbox.pop()  # O(1) amortized

    def peek(self):
        self._transfer()
        return self.outbox[-1]    # O(1) amortized

    def empty(self):
        return not self.inbox and not self.outbox

    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
            # inbox is now reversed into outbox → FIFO order restored

Why O(1) amortized? Each element is moved from inbox to outbox exactly once. Over n operations, total moves = n, so average cost per operation = O(1).

Canonical Problems

• Min Stack (Medium)

• Implement Queue using Stacks (Easy)

• Implement Stack using Queues (Easy)

When to Reach for Stack vs Queue vs Deque

NEW PROBLEM WITH LINEAR DATA
         │
         ▼
Need to process MOST RECENTLY SEEN element first?
  └─ Yes → STACK (LIFO)
         │
Need to process EARLIEST SEEN element first?
  └─ Yes → QUEUE (FIFO), especially for BFS
         │
Need O(1) access on BOTH ENDS?
  └─ Yes → DEQUE (double-ended queue)
         │
Need MINIMUM OR MAXIMUM in a sliding window?
  └─ Yes → MONOTONIC DEQUE
         │
Problem has NESTED structure (brackets, function calls)?
  └─ Yes → STACK
         │
Need to find NEXT GREATER / SMALLER element?
  └─ Yes → MONOTONIC STACK
         │
Problem involves LEVEL-BY-LEVEL tree/graph traversal?
  └─ Yes → QUEUE + BFS

The 10 Must-Know Problems

Solve 1–3 first (30 minutes each). Then 4–8 (45 minutes each). Then 9 and 10 — they're genuinely hard and will take time, but they complete your stack/queue toolkit.

Bottom Line

Stacks and queues are not warm-up questions. The monotonic stack alone unlocks a class of O(n) solutions that have no obvious alternative approach. The deque enables the sliding window maximum, which appears in variations across dozens of hard problems. BFS with a queue is the backbone of shortest-path problems in unweighted graphs.

Candidates who treat these structures as trivial have a systematic blind spot. The problems built on them are Medium and Hard precisely because recognizing "this is a monotonic stack problem" is not obvious. It becomes obvious only after you've studied the pattern deliberately.

Study the pattern. Recognize the trigger. Reach for the right structure in 30 seconds. That's the goal.

🧭 What's Next in This Series

Two posts remain in Chapter 2:

• Post 08: Trees & BST — the most tested structure in FAANG interviews: DFS, BFS, all traversal types, LCA, path sums, and BST validation with a framework that makes recursive tree thinking feel natural