Posted on Nov 3 • Edited on Nov 12

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:

Store indices in monotonic stacks for distance calculations
Check empty before pop to avoid errors
Remember operand order in non-commutative operations
Synchronize auxiliary stacks for property tracking
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.