BeginnerStacks, Queues, Heaps

Stack Simulation

Use stacks to parse structures, evaluate expressions, or simulate other data structures

Time: O(n)
Space: O(n)
Pattern Overview

Core Idea

Push state and pop when encountering matching delimiters or operators; two stacks for operator precedence or queue emulation.

When to Use

Use for parentheses validation, decoding strings, calculator problems, or building a queue from two stacks.

General Recognition Cues
General indicators that this pattern might be applicable
  • Matching brackets
  • Eval expressions
  • Reverse on close bracket
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Parentheses

Push on open, pop on matching close

When to Use This Variant
  • ()[]{} validation
Use Case
Syntax check
Advantages
  • Linear time
  • Simple
Implementation
def is_valid_parentheses(s):
    st = []
    mp = {')':'(', ']':'[', '}':'{'}
    for ch in s:
        if ch in '([{': st.append(ch)
        else:
            if not st or st.pop() != mp.get(ch): return False
    return not st
2

Decode/Eval

Use two stacks for numbers and ops/strings

When to Use This Variant
  • k[...]
  • Calculator
Use Case
Decoding/evaluation
Advantages
  • Deterministic
  • Handles nesting
Implementation
def decode_string(s):
    st_num, st_str = [], []
    cur, num = '', 0
    for ch in s:
        if ch.isdigit():
            num = num*10 + int(ch)
        elif ch == '[':
            st_num.append(num); st_str.append(cur)
            cur, num = '', 0
        elif ch == ']':
            times = st_num.pop(); prev = st_str.pop()
            cur = prev + cur * times
        else:
            cur += ch
    return cur
3

Two-Stack Queue

In/out stacks for amortized O(1) dequeues

When to Use This Variant
  • Queue by stacks
Use Case
Queue implementation
Advantages
  • Amortized O(1)
  • Simple
Implementation
class MyQueue:
    def __init__(self):
        self._in, self._out = [], []
    def push(self, x):
        self._in.append(x)
    def _move(self):
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())
    def pop(self):
        self._move(); return self._out.pop()
    def peek(self):
        self._move(); return self._out[-1]
    def empty(self):
        return not self._in and not self._out
Common Pitfalls
Watch out for these common mistakes
  • Operator precedence/associativity
  • Empty stack pops
  • Multi-digit parsing
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Each char/token processed once.

Space Complexity
O(n)

Stack holds nested state.

Ready to test your knowledge?

Test your pattern recognition with interactive questions