DSA Fundamentals: Stack - From Theory to LeetCode Practice

DSA Fundamentals: Stack - From Theory to LeetCode Practice

The Stack is one of the most fundamental data structures in computer science, following the Last In, First Out (LIFO) principle. Understanding stacks is essential for solving problems involving balanced expressions, undo operations, function call management, and many other algorithmic challenges.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core stack patterns.

Understanding Stack: LIFO Principle

Stack Fundamentals

Stack is a linear data structure that follows the LIFO (Last In, First Out) principle - the last element added is the first one to be removed. Think of it like a stack of trays at a restaurant: you add new trays on top and remove from the top.

Real-World Analogies

• Stack of plates: Add and remove from the top
• Browser history: Back button (most recent pages first)
• Undo functionality: Reverse most recent actions
• Function call stack: Most recent function call executes first

Stack Operations

Core Operations:

Operation	Description	Time Complexity	Python Implementation
push(x)	Add element to top	O(1)	stack.append(x)
pop()	Remove and return top element	O(1)	stack.pop()
peek() / top()	View top element without removing	O(1)	stack[-1]
isEmpty()	Check if stack is empty	O(1)	not stack or len(stack) == 0
size()	Get number of elements	O(1)	len(stack)

Python Stack Implementation

Using List (Array):

# Initialize empty stack
stack = []

# Push operations - O(1)
stack.append(1)
stack.append(2)
stack.append(3)
# Stack: [1, 2, 3] (3 is at top)

# Peek operation - O(1)
top_element = stack[-1]  # Returns 3

# Pop operation - O(1)
removed = stack.pop()  # Returns 3
# Stack: [1, 2]

# Check if empty - O(1)
is_empty = not stack  # Returns False
is_empty = len(stack) == 0  # Returns False

# Size operation - O(1)
size = len(stack)  # Returns 2

Using collections.deque (Recommended for complex scenarios):

from collections import deque

# Initialize
stack = deque()

# Operations (same interface)
stack.append(1)      # Push
top = stack[-1]      # Peek
removed = stack.pop() # Pop

Stack vs Array vs Queue

Feature	Stack (LIFO)	Queue (FIFO)	Array
Access Pattern	Last In, First Out	First In, First Out	Random Access
Primary Operations	push, pop (from end)	enqueue, dequeue (from both ends)	Access by index
Access Time	O(1) for top	O(1) for front/rear	O(1) for any index
Use Cases	Undo, recursion, parsing	Task scheduling, BFS	General storage, random access
Python Implementation	list with append/pop	deque with append/popleft	list

Essential LeetCode Problems & Solutions

Let's explore fundamental stack problems that demonstrate core algorithmic patterns.

1. Valid Parentheses (LeetCode 20)

Problem: Determine if a string containing brackets (), {}, [] is valid. Valid means:

• Open brackets must be closed by the same type
• Open brackets must be closed in correct order
• Every close bracket has corresponding open bracket

Examples:

• "()" → True
• "()[]{}" → True
• "(]" → False
• "([)]" → False (wrong order)

Approach: Use stack to track open brackets. When encountering close bracket, check if it matches most recent open bracket.

class Solution:
    def isValid(self, s: str) -> bool:
        # Map closing brackets to their opening counterparts
        bracket_map = {"}": "{", "]": "[", ")": "("}
        stack = []

        for char in s:
            # If it's an opening bracket
            if char not in bracket_map:
                stack.append(char)
            else:
                # It's a closing bracket
                # Check if stack is empty (no matching open bracket)
                if not stack:
                    return False

                # Pop most recent opening bracket
                popped = stack.pop()

                # Check if it matches the closing bracket
                if popped != bracket_map[char]:
                    return False

        # Valid if all brackets matched (stack empty)
        return not stack

Time Complexity: O(n) - Single pass through string

Space Complexity: O(n) - Stack can hold all opening brackets in worst case

Key Concepts:

• LIFO nature: Most recent opening bracket should match current closing bracket
• Hash map for pairing: Quick lookup of bracket pairs
• Empty stack check: Closing bracket without opening bracket
• Final stack check: All brackets must be matched (empty stack)

Edge Cases:

• Empty string: Valid (return True)
• Only opening brackets: Invalid (stack not empty)
• Only closing brackets: Invalid (stack empty when checking)
• Mismatched types: "([)]" - caught by matching check

2. Min Stack (LeetCode 155)

Problem: Design a stack that supports push, pop, top, and retrieving minimum element in constant time.

Operations Required:

• push(val): Push element onto stack
• pop(): Remove element from top
• top(): Get top element
• getMin(): Retrieve minimum element (O(1))

Approach: Use two stacks - one for data, one for tracking minimum values at each level.

class MinStack:
    def __init__(self):
        # Main stack for data
        self.data_stack = []
        # Stack to track minimum at each level
        self.min_stack = []

    def push(self, val: int) -> None:
        # Always push to data stack
        self.data_stack.append(val)

        # Push to min stack
        if not self.min_stack:
            # First element is the minimum
            self.min_stack.append(val)
        else:
            # Current minimum is min of new value and previous minimum
            current_min = self.min_stack[-1]
            self.min_stack.append(min(current_min, val))

    def pop(self) -> None:
        # Pop from both stacks to maintain sync
        self.data_stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        # Return top of data stack
        return self.data_stack[-1]

    def getMin(self) -> int:
        # Return top of min stack (current minimum)
        return self.min_stack[-1]


# Usage example:
# obj = MinStack()
# obj.push(-2)    # data: [-2],     min: [-2]
# obj.push(0)     # data: [-2, 0],  min: [-2, -2]
# obj.push(-3)    # data: [-2, 0, -3], min: [-2, -2, -3]
# obj.getMin()    # Returns -3
# obj.pop()       # data: [-2, 0],  min: [-2, -2]
# obj.top()       # Returns 0
# obj.getMin()    # Returns -2

Time Complexity: O(1) for all operations

Space Complexity: O(n) - Two stacks, each storing n elements

Key Concepts:

• Auxiliary stack pattern: Track additional information alongside main data
• Sync maintenance: Both stacks must stay synchronized
• Min tracking: Store minimum value at each stack level
• Trade-off: Space (extra stack) for time (O(1) min retrieval)

Why Two Stacks?

• Without min_stack: Finding minimum requires O(n) scan through data_stack
• With min_stack: Minimum always available at top in O(1)
• Space cost: O(n) extra space for guaranteed O(1) retrieval

Alternative Approach (Space Optimization):

# Store (value, current_min) tuples in single stack
class MinStack:
    def __init__(self):
        self.stack = []  # Store (value, min_at_this_level)

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = self.stack[-1][1]
            self.stack.append((val, min(val, current_min)))

    def pop(self) -> None:
        self.stack.pop()

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

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

3. Daily Temperatures (LeetCode 739)

Problem: Given array of daily temperatures, return array where answer[i] is the number of days until a warmer temperature. If no warmer day, use 0.

Example:

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output:               [ 1,  1,  4,  2,  1,  1,  0,  0]

Explanation:
- Day 0 (73°): Next warmer is day 1 (74°) → 1 day wait
- Day 1 (74°): Next warmer is day 2 (75°) → 1 day wait
- Day 2 (75°): Next warmer is day 6 (76°) → 4 days wait
- Day 6 (76°): No warmer day → 0

Approach: Use monotonic decreasing stack to track indices of temperatures waiting for warmer day.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Initialize result array with zeros
        result = [0] * len(temperatures)

        # Stack stores indices of temperatures waiting for warmer day
        stack = []

        for i, temp in enumerate(temperatures):
            # While current temp is warmer than temperatures in stack
            while stack and temperatures[stack[-1]] < temp:
                # Pop previous index
                prev_index = stack.pop()
                # Calculate days to wait
                result[prev_index] = i - prev_index

            # Add current index to stack
            stack.append(i)

        return result

Time Complexity: O(n) - Each element pushed and popped at most once

Space Complexity: O(n) - Stack can hold all indices in worst case

Key Concepts:

• Monotonic stack: Maintains decreasing temperature order
• Index storage: Store indices, not values, to calculate distance
• Next greater element pattern: Finding next element that satisfies condition
• Efficient lookup: O(1) amortized for finding next warmer day

Visualization:

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

i=0, temp=73: stack=[] → push 0 → stack=[0]
i=1, temp=74: 74>73 → pop 0, result[0]=1 → push 1 → stack=[1]
i=2, temp=75: 75>74 → pop 1, result[1]=1 → push 2 → stack=[2]
i=3, temp=71: 71<75 → push 3 → stack=[2,3]
i=4, temp=69: 69<71 → push 4 → stack=[2,3,4]
i=5, temp=72: 72>69 → pop 4, result[4]=1
              72>71 → pop 3, result[3]=2
              72<75 → push 5 → stack=[2,5]
i=6, temp=76: 76>72 → pop 5, result[5]=1
              76>75 → pop 2, result[2]=4
              push 6 → stack=[6]
i=7, temp=73: 73<76 → push 7 → stack=[6,7]

Remaining in stack get 0 (no warmer day found)

Why Monotonic Stack?

• Maintains order: Stack always has decreasing temperatures
• Efficient processing: When warmer temp found, resolve all colder temps in stack
• Single pass: Each element processed exactly once

4. Evaluate Reverse Polish Notation (LeetCode 150)

Problem: Evaluate arithmetic expression in Reverse Polish Notation (RPN). Valid operators: +, -, *, /.

Reverse Polish Notation:

• Operators come after operands
• No parentheses needed
• Left-to-right evaluation

Examples:

["2", "1", "+", "3", "*"] → ((2 + 1) * 3) = 9
["4", "13", "5", "/", "+"] → (4 + (13 / 5)) = 6
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
→ 22

Approach: Use stack to store operands. When encountering operator, pop two operands, apply operation, push result.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {"+", "-", "*", "/"}

        for token in tokens:
            if token not in operators:
                # It's a number, push to stack
                stack.append(int(token))
            else:
                # It's an operator, pop two operands
                # Note: LIFO order matters!
                second = stack.pop()  # Right operand
                first = stack.pop()   # Left operand

                # Perform operation
                if token == "+":
                    result = first + second
                elif token == "-":
                    result = first - second
                elif token == "*":
                    result = first * second
                elif token == "/":
                    # Integer division (truncate toward zero)
                    result = int(first / second)

                # Push result back to stack
                stack.append(result)

        # Final result is the only element in stack
        return stack[-1]

Time Complexity: O(n) - Single pass through tokens

Space Complexity: O(n) - Stack holds operands

Key Concepts:

• RPN evaluation: Natural fit for stack data structure
• Operand order: LIFO means second pop is first operand
• Intermediate results: Push back to stack for future operations
• Division truncation: Python's int() truncates toward zero

Important: Operand Order Matters!

# For subtraction: 5 - 3
stack = [5, 3]
second = stack.pop()  # 3
first = stack.pop()   # 5
result = first - second  # 5 - 3 = 2 ✓

# Wrong order would give: 3 - 5 = -2 ✗

Division Edge Case:

# Python division behavior
# Standard division: -3 / 2 = -1.5
# int() truncation: int(-1.5) = -1 (toward zero)
# Floor division: -3 // 2 = -2 (toward -infinity)

# For RPN, use int(a / b) for truncation toward zero

Step-by-step Example:

tokens = ["2", "1", "+", "3", "*"]

Step 1: "2" → stack = [2]
Step 2: "1" → stack = [2, 1]
Step 3: "+" → pop 1, pop 2 → 2+1=3 → stack = [3]
Step 4: "3" → stack = [3, 3]
Step 5: "*" → pop 3, pop 3 → 3*3=9 → stack = [9]
Result: 9

Core Stack Patterns

1. Balanced Expression Validation Pattern

When to use:

• Matching pairs (brackets, tags, quotes)
• Nested structures
• Balanced sequences

Examples: Valid Parentheses, Valid HTML Tags, Remove Invalid Parentheses

Template:

def validate_balanced(expression):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}  # closing -> opening

    for char in expression:
        if char not in pairs:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack or stack.pop() != pairs[char]:
                return False

    return not stack  # All matched if empty

Key characteristics:

• Use hash map for pair matching
• Stack stores opening elements
• Check stack emptiness at end

2. Monotonic Stack Pattern

When to use:

• Next greater/smaller element problems
• Finding spans or ranges
• Temperature, stock price problems

Examples: Daily Temperatures, Next Greater Element, Stock Span Problem

Monotonic Increasing Stack Template:

def next_greater_elements(arr):
    result = [-1] * len(arr)
    stack = []  # Stores indices

    for i in range(len(arr)):
        # Maintain increasing order
        while stack and arr[stack[-1]] < arr[i]:
            prev_index = stack.pop()
            result[prev_index] = arr[i]
        stack.append(i)

    return result

Monotonic Decreasing Stack Template:

def next_smaller_elements(arr):
    result = [-1] * len(arr)
    stack = []  # Stores indices

    for i in range(len(arr)):
        # Maintain decreasing order
        while stack and arr[stack[-1]] > arr[i]:
            prev_index = stack.pop()
            result[prev_index] = arr[i]
        stack.append(i)

    return result

Key characteristics:

• Store indices, not values (to calculate distances)
• Maintain increasing or decreasing order
• O(n) time - each element pushed/popped once

3. Expression Evaluation Pattern

When to use:

• Calculator problems
• Postfix/prefix notation
• Expression parsing

Examples: Evaluate RPN, Basic Calculator, Expression Parsing

Template:

def evaluate_postfix(tokens):
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in tokens:
        if token not in operators:
            stack.append(int(token))
        else:
            b = stack.pop()  # Right operand
            a = stack.pop()  # Left operand
            result = apply_operation(a, b, token)
            stack.append(result)

    return stack[-1]

Key characteristics:

• Stack stores operands/intermediate results
• Operators trigger pop and computation
• Order matters for non-commutative operations

4. Auxiliary Stack Pattern (Min/Max Tracking)

When to use:

• Need to track additional property (min, max, etc.)
• O(1) retrieval of special element required
• Stack modifications affect tracked property

Examples: Min Stack, Max Stack, Stack with getMin()

Template:

class SpecialStack:
    def __init__(self):
        self.data_stack = []
        self.special_stack = []  # Tracks min/max/etc

    def push(self, val):
        self.data_stack.append(val)
        if not self.special_stack:
            self.special_stack.append(val)
        else:
            # Update special property
            current_special = self.special_stack[-1]
            new_special = combine(current_special, val)
            self.special_stack.append(new_special)

    def pop(self):
        self.data_stack.pop()
        self.special_stack.pop()

    def get_special(self):
        return self.special_stack[-1]

Key characteristics:

• Two synchronized stacks
• Trade space for O(1) retrieval
• Both stacks must stay in sync

Performance Optimization Tips

1. Choose Right Container

# For simple stack operations: Use list
stack = []
stack.append(1)  # O(1)
stack.pop()      # O(1)

# For deque operations (both ends): Use collections.deque
from collections import deque
stack = deque()
stack.append(1)      # O(1)
stack.pop()          # O(1)
stack.appendleft(1)  # O(1) - bonus operation

Key insight: Python list is optimized for stack operations. Use deque only if you need operations on both ends.

2. Store Indices vs Values in Monotonic Stack

# Store indices (more flexible)
def next_greater_with_distance(arr):
    result = [-1] * len(arr)
    stack = []  # Store indices

    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx  # Can calculate distance
        stack.append(i)
    return result

# Store values (only if distance not needed)
def next_greater_simple(arr):
    stack = []  # Store values
    result = []

    for num in reversed(arr):
        while stack and stack[-1] <= num:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(num)

    return result[::-1]

Key insight: Store indices when you need to calculate distances or positions.

3. Avoid Unnecessary Operations

# Inefficient: Check same condition multiple times
for token in tokens:
    if token == "+":
        result = a + b
    elif token == "-":
        result = a - b
    elif token == "*":
        result = a * b
    elif token == "/":
        result = a / b
    stack.append(result)

# Efficient: Use dictionary for operator dispatch
operators = {
    '+': lambda a, b: a + b,
    '-': lambda a, b: a - b,
    '*': lambda a, b: a * b,
    '/': lambda a, b: int(a / b)
}

for token in tokens:
    if token in operators:
        b, a = stack.pop(), stack.pop()
        stack.append(operators[token](a, b))
    else:
        stack.append(int(token))

4. Early Termination in Validation

# Optimized: Return False immediately
def is_valid(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        else:
            if not stack:  # Early termination
                return False
            stack.pop()
    return not stack

# Also check impossible cases early
def is_valid(s):
    if len(s) % 2 != 0:  # Odd length can't be balanced
        return False
    # ... rest of logic

Common Pitfalls and Solutions

1. Forgetting to Check Empty Stack

# Wrong: Potential error on empty stack
def process_stack(stack):
    top = stack.pop()  # Error if stack empty!

# Correct: Always check before pop
def process_stack(stack):
    if not stack:
        return None
    top = stack.pop()
    return top

# Or use try-except
def process_stack(stack):
    try:
        return stack.pop()
    except IndexError:
        return None

2. Wrong Operand Order in RPN

# Wrong: Reversed operands
second = stack.pop()
first = stack.pop()
result = second - first  # Wrong! Should be first - second

# Correct: Remember LIFO order
second = stack.pop()  # Popped second, was pushed second
first = stack.pop()   # Popped first, was pushed first
result = first - second  # Correct order for subtraction

3. Not Handling Final Stack State

# Wrong: Assume stack has exactly one element
def evaluate(tokens):
    stack = []
    # ... process tokens ...
    return stack[-1]  # What if stack is empty or has multiple elements?

# Correct: Validate final state
def evaluate(tokens):
    stack = []
    # ... process tokens ...
    if len(stack) != 1:
        raise ValueError("Invalid expression")
    return stack[0]

4. Confusing Peek vs Pop

# Wrong: Pop when you just want to look
def check_top(stack):
    top = stack.pop()  # Modifies stack!
    return top == target

# Correct: Peek without modifying
def check_top(stack):
    if not stack:
        return False
    return stack[-1] == target  # Just look, don't pop

5. Integer Division in Python

# Wrong: Floor division for RPN
result = first // second  # -3 // 2 = -2 (wrong for RPN)

# Correct: Truncate toward zero
result = int(first / second)  # int(-3 / 2) = int(-1.5) = -1

# Explanation:
# Floor division (//): Always rounds toward -infinity
# int() truncation: Rounds toward zero
# RPN expects truncation toward zero

Stack Time Complexity Summary

Problem	Approach	Time Complexity	Space Complexity
Valid Parentheses	Stack matching	O(n)	O(n)
Min Stack	Auxiliary stack	O(1) per operation	O(n)
Daily Temperatures	Monotonic stack	O(n)	O(n)
Evaluate RPN	Stack evaluation	O(n)	O(n)
Next Greater Element	Monotonic stack	O(n)	O(n)
Basic Calculator	Stack with operators	O(n)	O(n)

Key Insights:

• Push/Pop: Always O(1)
• Full processing: O(n) - each element touched constant times
• Monotonic stack: O(n) - each element pushed/popped at most once
• Space: Usually O(n) worst case for stack storage

Queue Quick Overview

Queue follows FIFO (First In, First Out) - like a line at a store. The first person to arrive is the first to be served.

Queue Operations

Operation	Description	Time Complexity	Python Implementation
enqueue(x)	Add element to rear	O(1)	queue.append(x)
dequeue()	Remove element from front	O(1)	queue.popleft()
front()	View front element	O(1)	queue[0]
isEmpty()	Check if empty	O(1)	not queue

Python Queue Implementation

from collections import deque

# Initialize queue
queue = deque()

# Enqueue (add to rear)
queue.append(1)
queue.append(2)
queue.append(3)
# Queue: [1, 2, 3] (1 is front, 3 is rear)

# Dequeue (remove from front)
front = queue.popleft()  # Returns 1
# Queue: [2, 3]

# Peek front
front_element = queue[0]  # Returns 2

# Check empty
is_empty = len(queue) == 0  # Returns False

Note: We'll explore Queue in depth when covering Tree traversal (BFS) and other graph algorithms where Queue is the primary data structure.

Conclusion

Stack is a fundamental data structure with elegant solutions to many algorithmic problems. Key takeaways:

Core Concepts Mastered:

Stack Fundamentals:

• LIFO principle: Last In, First Out access pattern
• O(1) operations: Push, pop, peek all constant time
• Python implementation: List with append/pop
• Use cases: Parsing, expression evaluation, backtracking

Essential Patterns Mastered:

Pattern 1: Balanced expression validation (Valid Parentheses)

Pattern 2: Monotonic stack for next greater/smaller (Daily Temperatures)

Pattern 3: Expression evaluation (Evaluate RPN)

Pattern 4: Auxiliary stack for tracking properties (Min Stack)

Problem-Solving Strategies:

• Matching pairs: Use stack with hash map for pair validation
• Next greater/smaller: Use monotonic stack pattern
• Expression evaluation: Natural fit for stack (RPN, calculators)
• Track min/max: Auxiliary stack maintains property in O(1)
• Nested structures: Stack handles arbitrary nesting depth

Key Optimization Principles:

1. Store indices in monotonic stacks for distance calculations
2. Check empty before pop to avoid errors
3. Remember operand order in non-commutative operations
4. Synchronize auxiliary stacks for property tracking
5. Use early termination in validation problems

When to Use Stack:

• Need to reverse order or process in LIFO manner
• Matching/balancing problems (parentheses, tags)
• Next greater/smaller element problems
• Expression parsing and evaluation
• Backtracking and undo operations
• Function call simulation

Next Steps:

Building on stack foundations, future topics will cover:

• Queue and BFS (Tree level-order traversal)
• Binary Trees and Traversals (using stack for DFS)
• Graph Algorithms (DFS with stack, BFS with queue)
• Backtracking (stack-based state management)

The problems covered here represent fundamental stack patterns that appear across technical interviews and competitive programming. Master these patterns, and you'll recognize stack opportunities in complex problems.

---

Practice Problems for Mastery:

Stack Fundamentals:

• 20. Valid Parentheses
• 155. Min Stack
• 232. Implement Queue using Stacks
• 225. Implement Stack using Queues
• 1047. Remove All Adjacent Duplicates in String

Monotonic Stack:

• 739. Daily Temperatures
• 496. Next Greater Element I
• 503. Next Greater Element II
• 84. Largest Rectangle in Histogram
• 42. Trapping Rain Water

Expression Evaluation:

• 150. Evaluate Reverse Polish Notation
• 224. Basic Calculator
• 227. Basic Calculator II
• 772. Basic Calculator III

Advanced Stack:

• 394. Decode String
• 716. Max Stack
• 895. Maximum Frequency Stack
• 946. Validate Stack Sequences

References:

• NeetCode - Algorithms
• LeetCode Patterns
• Greg Hogg DSA Algorithm YouTube Channel
• Algorithm Design Manual by Steven Skiena
• Introduction to Algorithms by Cormen et al.

This comprehensive guide provides a solid foundation for mastering stack data structures and recognizing stack patterns in algorithmic problem-solving.