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'sint()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.
SOCIAL SHARE CARD GENERATOR