Stack and Queue Interview Patterns — 15+ Patterns Catalog

Stacks and queues appear in interviews more than almost any other data structure. This article catalogs 15+ patterns with recognition signals, Python templates, and the problems they solve. Bookmark this as your interview pattern reference.

Pattern Decision Flowchart

Does the problem involve...
├── Matching/nesting (brackets, tags, HTML)?
│   └── Pattern 1: Bracket Matching
├── "Next greater/smaller" or span?
│   └── Pattern 2: Monotonic Stack
├── Expression evaluation or parsing?
│   └── Pattern 3: Expression Stack
├── BFS / shortest path / level order?
│   └── Pattern 4-7: Queue BFS variants
├── "Design a data structure"?
│   └── Pattern 8-10: Design patterns
├── Undo/redo or history?
│   └── Pattern 11: Two-Stack History
├── Sliding window min/max?
│   └── Pattern 12: Monotonic Deque
└── Simulation of stack/queue behavior?
    └── Pattern 13-15: Simulation patterns

---

Stack Patterns

Pattern 1: Bracket Matching

Signal: Matching parentheses, brackets, tags, or nested structures.

def is_valid(s: str) -> bool:
    """Template: bracket matching."""
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    return not stack

Problems: Valid Parentheses (LC 20), Valid Parenthesis String (LC 678), Tag Validator (LC 591), Remove Invalid Parentheses (LC 301).

---

Pattern 2: Monotonic Stack

Signal: “Next greater”, “next smaller”, “previous greater”, spans, or histogram-type problems.

def next_greater(arr):
    """Template: monotonic decreasing stack."""
    n = len(arr)
    result = [-1] * n
    stack = []  # indices
    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

Variants:

• Monotonic decreasing stack → next greater element
• Monotonic increasing stack → next smaller element
• Iterate right to left → previous greater/smaller

Problems: Next Greater Element I/II (LC 496, 503), Daily Temperatures (LC 739), Largest Rectangle in Histogram (LC 84), Stock Span (LC 901).

---

Pattern 3: Expression Evaluation

Signal: Evaluate math expressions, calculators, nested operations with parentheses.

def calculate(s: str) -> int:
    """Template: expression evaluation with stack."""
    stack = []
    num = 0
    sign = 1
    result = 0

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

    return result + sign * num

Problems: Basic Calculator I/II/III (LC 224, 227, 772), Evaluate RPN (LC 150), Decode String (LC 394).

---

Pattern 4: Stack as Recursion Simulation

Signal: Tree traversals iteratively, or converting recursive DFS to iterative.

def inorder_iterative(root):
    """Template: iterative inorder traversal."""
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

Problems: Inorder Traversal (LC 94), Preorder (LC 144), Flatten Binary Tree (LC 114).

---

Pattern 5: Min/Max Stack

Signal: “Get minimum/maximum in O(1)” alongside push/pop.

class MinStack:
    """Template: track min alongside each element."""
    def __init__(self):
        self.stack = []  # (value, current_min)

    def push(self, val):
        min_val = min(val, self.stack[-1][1] if self.stack else val)
        self.stack.append((val, min_val))

    def pop(self):
        return self.stack.pop()[0]

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

Problems: Min Stack (LC 155), Max Stack (LC 716), Max Frequency Stack (LC 895).

---

Queue Patterns

Pattern 6: Standard BFS

Signal: Shortest path in unweighted graph, level-order traversal, “minimum moves”.

from collections import deque

def bfs(graph, start, target):
    """Template: standard BFS shortest path."""
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

Problems: Word Ladder (LC 127), Open the Lock (LC 752), Shortest Path in Binary Matrix (LC 1091).

---

Pattern 7: Multi-Source BFS

Signal: Multiple starting points, “distance from nearest X”, “rotting” problems.

def multi_source_bfs(grid, sources):
    """Template: BFS from all sources simultaneously."""
    queue = deque()
    visited = set()
    for r, c in sources:
        queue.append((r, c, 0))
        visited.add((r, c))
    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
                if (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, dist + 1))

Problems: Rotting Oranges (LC 994), Walls and Gates (LC 286), 01 Matrix (LC 542).

---

Pattern 8: Level-Order BFS

Signal: Process nodes level by level, zigzag, right side view.

def level_order(root):
    """Template: level-by-level BFS."""
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Problems: Level Order Traversal (LC 102), Zigzag (LC 103), Right Side View (LC 199), Average of Levels (LC 637).

---

Pattern 9: Monotonic Deque (Sliding Window)

Signal: Sliding window minimum/maximum, “max in every window of size k”.

def max_sliding_window(nums, k):
    """Template: monotonic decreasing deque for sliding window max."""
    dq = deque()  # indices, front is always the max
    result = []
    for i, num in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller elements (they cannot be max)
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Problems: Sliding Window Maximum (LC 239), Shortest Subarray with Sum at Least K (LC 862), Jump Game VI (LC 1696).

---

Pattern 10: Stack for String Building / Simplification

Signal: Remove characters, simplify paths, deduplicate, “remove k digits”.

def remove_duplicates(s: str) -> str:
    """Template: stack for character removal."""
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Problems: Remove All Adjacent Duplicates (LC 1047), Remove K Digits (LC 402), Simplify Path (LC 71), Remove Duplicate Letters (LC 316).

---

Pattern 11: Two-Stack History (Undo/Redo)

Signal: Browser history, undo/redo, back/forward navigation.

class BrowserHistory:
    """Template: two-stack navigation."""
    def __init__(self, homepage):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url):
        self.back_stack.append(url)
        self.forward_stack.clear()  # clear forward history

    def back(self, steps):
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps):
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

Problems: Design Browser History (LC 1472), Implement Queue using Stacks (LC 232).

---

Pattern 12: Stack Sort / Reorganize

Signal: Sort a stack, validate a sequence of push/pop operations.

def sort_stack(stack):
    """Template: sort stack using auxiliary stack."""
    aux = []
    while stack:
        temp = stack.pop()
        while aux and aux[-1] > temp:
            stack.append(aux.pop())
        aux.append(temp)
    return aux

Problems: Sort a Stack (LC interview classic), Validate Stack Sequences (LC 946).

---

Pattern 13: Priority Queue / Heap BFS (0-1 BFS)

Signal: Graph with edge weights 0 or 1, shortest path with two types of edges.

def zero_one_bfs(graph, start):
    """Template: 0-1 BFS using deque."""
    dist = {start: 0}
    dq = deque([start])
    while dq:
        node = dq.popleft()
        for neighbor, weight in graph[node]:
            new_dist = dist[node] + weight
            if neighbor not in dist or new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                if weight == 0:
                    dq.appendleft(neighbor)
                else:
                    dq.append(neighbor)
    return dist

Problems: Minimum Cost to Make at Least One Valid Path (LC 1368), Shortest Path with Alternating Colors (LC 1129).

---

Pattern 14: Topological Sort (Kahn’s / Queue)

Signal: Dependencies, course scheduling, ordering with prerequisites.

from collections import deque, defaultdict

def topological_sort(n, edges):
    """Template: Kahn's algorithm with queue."""
    indegree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # empty = cycle

Problems: Course Schedule I/II (LC 207, 210), Alien Dictionary (LC 269).

---

Pattern 15: Deque for Double-Ended Operations

Signal: Push/pop from both ends, palindrome checking, design problems.

from collections import deque

# Palindrome check
def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

Problems: Design Circular Deque (LC 641), Front Middle Back Queue (LC 1670).

---

Quick Reference Table

Pattern	Signal Words	Data Structure	Complexity
Bracket Matching	”valid”, “balanced”, “matching”	Stack	O(n)
Monotonic Stack	”next greater”, “span”, “histogram”	Stack	O(n)
Expression Eval	”calculate”, “evaluate”, “parse”	Stack	O(n)
Standard BFS	”shortest path”, “minimum moves”	Queue	O(V+E)
Multi-Source BFS	”nearest”, “rotting”, “spreading”	Queue	O(V+E)
Level-Order BFS	”level by level”, “zigzag”	Queue	O(n)
Monotonic Deque	”sliding window max/min”	Deque	O(n)
String Stack	”remove”, “simplify”, “deduplicate”	Stack	O(n)
Min/Max Stack	”O(1) min/max with push/pop”	Stack	O(1) per op
Topological Sort	”prerequisites”, “ordering”	Queue	O(V+E)

Interview Strategy

1. Read the problem — identify signal words from the table above
2. Pick the pattern — match signals to the appropriate template
3. Confirm with examples — trace through the template with the given input
4. Code the template — adapt it to the specific problem
5. Handle edge cases — empty input, single element, all same values

Key Takeaways

• Most stack/queue interview problems fit one of these 15 patterns
• Pattern recognition is faster than deriving solutions from scratch
• Signal words in problem statements map directly to patterns
• Practice 2-3 problems per pattern for interview readiness
• When stuck, ask yourself: “What do I need to remember?” (stack) or “What order should I process?” (queue)