Comprehensive Guide to Stacks
1. Foundational Understanding
1.1 What is a Stack?
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed. Think of it as a stack of plates: you can only add or remove plates from the top.
Key Characteristics:
- LIFO ordering: Last element inserted is first to be removed
- Restricted access: Can only access the top element
- Two primary operations: Push (add) and Pop (remove)
- Single entry/exit point: All operations occur at the top
Real-World Analogies:
- Stack of plates in a cafeteria
- Browser's back button (navigation history)
- Undo mechanism in text editors
- Call stack in programming languages
- Stack of books on a desk
1.2 Why Use Stacks?
Problem-Solving Benefits:
- Natural recursion simulation: Stacks mirror recursive call behavior
- Expression evaluation: Perfect for parsing and evaluating mathematical expressions
- Reversing sequences: LIFO property naturally reverses order
- Backtracking: Supports undo operations and state tracking
- Parsing and syntax checking: Ideal for balanced parentheses and bracket matching
When to Use Stacks:
- Function call management (call stack)
- Expression conversion and evaluation
- Syntax parsing (compilers, parsers)
- Backtracking algorithms (maze solving, puzzle solving)
- Browser history navigation
- Undo/Redo functionality
- Depth-First Search (DFS) traversal
- Reversing data
When NOT to Use Stacks:
- Need random access to elements (use array/list)
- FIFO ordering required (use queue instead)
- Need to access elements in middle (use array/linked list)
- Frequent search operations (use hash table/tree)
1.3 Stack Operations Overview
Core Operations:
class Stack:
"""Basic stack interface"""
def push(self, item):
"""Add item to top - O(1)"""
pass
def pop(self):
"""Remove and return top item - O(1)"""
pass
def peek(self):
"""View top item without removing - O(1)"""
pass
def is_empty(self):
"""Check if stack is empty - O(1)"""
pass
def size(self):
"""Get number of elements - O(1)"""
pass
Visual Representation:
Push operations: Pop operations:
Push 1 Push 2 Push 3 Pop Pop Pop
---- ---- ---- ---- ---- ----
→ | 2 | → | 3 | → | 2 | → | 1 | → empty
| 1 | | 1 | | 2 | | 1 |
---- ---- | 1 | ----
----
Top Top Top Top Top
1.4 Classification of Stack Topics
By Implementation:
- Array-based stack: Fixed/dynamic size using arrays
- Linked list-based stack: Dynamic size using linked list nodes
By Functionality:
- Basic stack: Standard push/pop/peek operations
- Min/Max stack: Track minimum/maximum with O(1) retrieval
- Monotonic stack: Maintains elements in monotonic order
By Application Domain:
- Expression handling: Infix, prefix, postfix evaluation
- Syntax checking: Balanced parentheses and brackets
- Sequence problems: Next greater element, stock span
- Algorithmic patterns: Backtracking, DFS traversal
- Data structure composition: Implementing queues using stacks
1.5 Stack in Different Contexts
In Programming Languages:
- Call Stack: Manages function calls and local variables
- Stack memory: Automatic memory allocation for local variables
- Stack frames: Each function call creates a stack frame
In Algorithms:
- DFS traversal: Uses stack for backtracking
- Topological sort: Stack-based implementation
- Expression parsing: Shunting-yard algorithm
- Backtracking: State management in puzzles/mazes
In System Design:
- Browser navigation: Back/forward buttons
- Text editors: Undo/redo functionality
- Expression calculators: RPN calculators
- Syntax validators: Compiler design
2. Theory and Principles
2.1 LIFO Principle
Core Concept: Last-In-First-Out (LIFO) is the fundamental principle governing stack behavior.
def demonstrate_lifo():
"""LIFO principle demonstration"""
stack = []
# Add elements in order: A, B, C
stack.append('A')
stack.append('B')
stack.append('C')
# Remove elements in reverse: C, B, A
print(stack.pop()) # C (last in, first out)
print(stack.pop()) # B
print(stack.pop()) # A (first in, last out)
Mathematical Formalization:
For a stack S with operations:
push(x): S → S ∪ {x}pop(): S → S \ {top(S)}, returns top(S)top(S): Returns most recently added element
Properties:
- If elements are pushed in order: e₁, e₂, e₃, ..., eₙ
- They will be popped in reverse: eₙ, eₙ₋₁, ..., e₂, e₁
- At any time t, the accessible element is the one most recently pushed
2.2 Stack as Abstract Data Type (ADT)
ADT Specification:
ADT Stack:
Data:
- Collection of elements with linear ordering
- Top pointer indicating current top element
Operations:
- push(item): Add item to top
Precondition: Stack not full (if bounded)
Postcondition: item is new top element
- pop(): Remove and return top element
Precondition: Stack not empty
Postcondition: Previous second element is new top
- peek(): Return top element without removal
Precondition: Stack not empty
Postcondition: Stack unchanged
- isEmpty(): Return true if stack empty
Precondition: None
Postcondition: Stack unchanged
2.3 Mathematical Properties
Stack Sequences:
Not all permutations of input sequence are possible output sequences from a stack.
def is_valid_stack_sequence(pushed, popped):
"""
Determine if popped sequence is valid for given pushed sequence
Theory: A sequence is valid if it can be achieved through
a series of push and pop operations
"""
stack = []
pop_index = 0
for push_val in pushed:
stack.append(push_val)
# Pop while top matches expected
while stack and stack[-1] == popped[pop_index]:
stack.pop()
pop_index += 1
return len(stack) == 0
# Example:
# Input: [1, 2, 3], Output: [3, 2, 1] - VALID
# Input: [1, 2, 3], Output: [3, 1, 2] - INVALID
Catalan Number Connection:
The number of valid stack sequences for n elements is the nth Catalan number:
Cₙ = (2n)! / ((n+1)! × n!)
Examples:
- n=1: C₁ = 1 (sequence: [1])
- n=2: C₂ = 2 (sequences: [2,1], [1,2])
- n=3: C₃ = 5 (sequences: [3,2,1], [2,3,1], [2,1,3], [1,3,2], [1,2,3])
2.4 Expression Evaluation Theory
Notation Types:
-
Infix: Operator between operands (A + B)
- Human-readable but requires precedence rules
- Needs parentheses for clarity
-
Prefix (Polish): Operator before operands (+ A B)
- No parentheses needed
- Evaluation: Right to left
-
Postfix (Reverse Polish): Operator after operands (A B +)
- No parentheses needed
- Evaluation: Left to right
- Easiest for computer evaluation
Conversion Theory:
Infix to Postfix Algorithm (Shunting-yard):
1. Read infix expression left to right
2. If operand: append to output
3. If operator:
- Pop operators with >= precedence to output
- Push current operator to stack
4. If '(': push to stack
5. If ')': pop until '(' found
6. At end: pop all remaining operators
Example:
Infix: A + B * C
Process: A → +[+] → B → *[+,*] → C → [+,*]
Postfix: A B C * +
Precedence and Associativity:
def get_precedence(operator):
"""Define operator precedence"""
precedence = {
'+': 1, '-': 1,
'*': 2, '/': 2, '%': 2,
'^': 3
}
return precedence.get(operator, 0)
def get_associativity(operator):
"""Define operator associativity"""
# Most operators are left-associative
# '^' (power) is right-associative
return 'R' if operator == '^' else 'L'
2.5 Monotonic Stack Theory
Concept: A monotonic stack maintains elements in monotonically increasing or decreasing order.
Types:
-
Monotonic Increasing: Each element > previous element
Bottom [...5, 7, 9] Top -
Monotonic Decreasing: Each element < previous element
Bottom [...9, 7, 5] Top
Key Insight:
When pushing element x:
- For increasing stack: Pop all elements < x
- For decreasing stack: Pop all elements > x
Applications:
- Next Greater Element
- Stock Span Problem
- Largest Rectangle in Histogram
- Trapping Rain Water
Template:
def monotonic_stack_pattern(arr, increasing=True):
"""
Generic monotonic stack pattern
increasing=True: maintains increasing order
increasing=False: maintains decreasing order
"""
stack = []
result = []
for i, num in enumerate(arr):
if increasing:
# Pop elements smaller than current
while stack and arr[stack[-1]] < num:
index = stack.pop()
# Process popped element
result.append((index, i)) # Example: store range
stack.append(i)
else:
# Pop elements larger than current
while stack and arr[stack[-1]] > num:
index = stack.pop()
result.append((index, i))
stack.append(i)
return result
2.6 Backtracking Theory with Stacks
Principle: Stack naturally supports backtracking by maintaining state history.
State Space Tree:
[Initial State]
/ | \
[Choice 1] [Choice 2] [Choice 3]
/ \ | \
[C1.1][C1.2] [C2.1] [C3.1]
Stack-based exploration:
1. Push initial state
2. Pop state, explore children
3. If dead-end, backtrack (pop)
4. If solution, record and continue/terminate
Stack vs Recursion:
- Recursion uses implicit call stack
- Explicit stack provides same functionality with more control
def backtrack_recursive(state):
"""Recursive backtracking"""
if is_solution(state):
record_solution(state)
return
for choice in get_choices(state):
make_choice(state, choice)
backtrack_recursive(state)
undo_choice(state, choice) # Backtrack
def backtrack_iterative(initial_state):
"""Stack-based backtracking"""
stack = [initial_state]
while stack:
state = stack.pop()
if is_solution(state):
record_solution(state)
continue
for choice in get_choices(state):
new_state = apply_choice(state, choice)
stack.append(new_state)
2.7 Stack Frame Theory
Call Stack Structure:
Each function call creates a stack frame containing:
- Return address
- Parameters
- Local variables
- Saved registers
Call Stack During Execution:
factorial(3)
├─ factorial(2)
│ ├─ factorial(1)
│ │ └─ factorial(0) ← Current frame
Stack Frames:
+------------------+ ← Top (current)
| factorial(0) |
| ret_addr, n=0 |
+------------------+
| factorial(1) |
| ret_addr, n=1 |
+------------------+
| factorial(2) |
| ret_addr, n=2 |
+------------------+
| factorial(3) |
| ret_addr, n=3 |
+------------------+ ← Bottom (first call)
3. Implementation and Mechanics
3.1 Array-Based Stack Implementation
Fixed-Size Array Stack:
class ArrayStack:
"""
Array-based stack with fixed capacity
Pros:
- Cache-friendly (contiguous memory)
- Simple implementation
- Fast operations (no pointer dereferencing)
Cons:
- Fixed size (can overflow)
- Wasted space if underutilized
"""
def __init__(self, capacity=100):
self.capacity = capacity
self.data = [None] * capacity
self.top_index = -1 # -1 indicates empty stack
def push(self, item):
"""O(1) - Add item to top"""
if self.is_full():
raise OverflowError("Stack is full")
self.top_index += 1
self.data[self.top_index] = item
def pop(self):
"""O(1) - Remove and return top item"""
if self.is_empty():
raise IndexError("Stack is empty")
item = self.data[self.top_index]
self.data[self.top_index] = None # Help garbage collection
self.top_index -= 1
return item
def peek(self):
"""O(1) - View top item without removing"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.data[self.top_index]
def is_empty(self):
"""O(1) - Check if stack is empty"""
return self.top_index == -1
def is_full(self):
"""O(1) - Check if stack is full"""
return self.top_index == self.capacity - 1
def size(self):
"""O(1) - Get number of elements"""
return self.top_index + 1
def __str__(self):
"""String representation (bottom to top)"""
if self.is_empty():
return "Stack: []"
elements = self.data[:self.top_index + 1]
return f"Stack: {elements} ← Top"
def clear(self):
"""O(1) - Clear all elements"""
self.data = [None] * self.capacity
self.top_index = -1
Dynamic Array Stack (Python List):
class DynamicArrayStack:
"""
Dynamic array-based stack (most common in Python)
Pros:
- No size limit
- Simple and intuitive
- Amortized O(1) push
Cons:
- Occasional O(n) resize cost
- May waste memory during resizing
"""
def __init__(self):
self.items = []
def push(self, item):
"""Amortized O(1) - Add item to top"""
self.items.append(item)
def pop(self):
"""O(1) - Remove and return top item"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
"""O(1) - View top item"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1]
def is_empty(self):
"""O(1) - Check if empty"""
return len(self.items) == 0
def size(self):
"""O(1) - Get size"""
return len(self.items)
def __str__(self):
return f"Stack: {self.items} ← Top"
# Most Pythonic way
stack = []
stack.append(item) # push
item = stack.pop() # pop
top = stack[-1] # peek
is_empty = len(stack) == 0
3.2 Linked List-Based Stack Implementation
Singly Linked List Stack:
class Node:
"""Node for linked list stack"""
def __init__(self, data):
self.data = data
self.next = None
class LinkedStack:
"""
Linked list-based stack
Pros:
- No fixed size limit
- No wasted space
- Efficient memory usage for small stacks
Cons:
- Extra memory for pointers
- Poor cache locality
- Slower than array for small operations
"""
def __init__(self):
self.top_node = None
self._size = 0
def push(self, item):
"""O(1) - Add item to top"""
new_node = Node(item)
new_node.next = self.top_node
self.top_node = new_node
self._size += 1
def pop(self):
"""O(1) - Remove and return top item"""
if self.is_empty():
raise IndexError("Stack is empty")
item = self.top_node.data
self.top_node = self.top_node.next
self._size -= 1
return item
def peek(self):
"""O(1) - View top item"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.top_node.data
def is_empty(self):
"""O(1) - Check if empty"""
return self.top_node is None
def size(self):
"""O(1) - Get size"""
return self._size
def __str__(self):
"""String representation"""
if self.is_empty():
return "Stack: [] ← Top"
elements = []
current = self.top_node
while current:
elements.append(current.data)
current = current.next
return f"Stack: {elements[::-1]} → {elements[0]} ← Top"
def clear(self):
"""O(1) - Clear stack"""
self.top_node = None
self._size = 0
3.3 Min Stack Implementation
Track Minimum with O(1) Retrieval:
class MinStack:
"""
Stack with O(1) getMin operation
Approach 1: Two stacks - main stack and min stack
"""
def __init__(self):
self.stack = []
self.min_stack = [] # Tracks minimum at each level
def push(self, val):
"""O(1) - Push value"""
self.stack.append(val)
# Push to min_stack: current min or new value if smaller
if not self.min_stack:
self.min_stack.append(val)
else:
self.min_stack.append(min(val, self.min_stack[-1]))
def pop(self):
"""O(1) - Pop value"""
if not self.stack:
raise IndexError("Stack is empty")
self.min_stack.pop()
return self.stack.pop()
def top(self):
"""O(1) - Get top value"""
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1]
def getMin(self):
"""O(1) - Get minimum value"""
if not self.min_stack:
raise IndexError("Stack is empty")
return self.min_stack[-1]
# Space-optimized version
class MinStackOptimized:
"""
Space-optimized: Only store min when it changes
"""
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
# Only push to min_stack if new minimum or equal
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if not self.stack:
raise IndexError("Stack is empty")
val = self.stack.pop()
# Only pop from min_stack if it was a minimum
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def getMin(self):
if not self.min_stack:
raise IndexError("Stack is empty")
return self.min_stack[-1]
# Single stack approach with encoding
class MinStackSingleStack:
"""
Single stack approach: Store (value, current_min) tuples
"""
def __init__(self):
self.stack = []
def push(self, val):
if not self.stack:
self.stack.append((val, val))
else:
current_min = min(val, self.stack[-1][1])
self.stack.append((val, current_min))
def pop(self):
if not self.stack:
raise IndexError("Stack is empty")
return self.stack.pop()[0]
def top(self):
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1][0]
def getMin(self):
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1][1]
3.4 Implementing Queue Using Stacks
Two Stack Approach:
class QueueUsingStacks:
"""
Implement queue using two stacks
Stack 1 (input): For enqueue operations
Stack 2 (output): For dequeue operations
Amortized O(1) for all operations
"""
def __init__(self):
self.input_stack = []
self.output_stack = []
def enqueue(self, item):
"""O(1) - Add to rear"""
self.input_stack.append(item)
def dequeue(self):
"""Amortized O(1) - Remove from front"""
# Move elements from input to output if output is empty
if not self.output_stack:
if not self.input_stack:
raise IndexError("Queue is empty")
# Transfer all elements (reverses order)
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
return self.output_stack.pop()
def peek(self):
"""Amortized O(1) - View front element"""
if not self.output_stack:
if not self.input_stack:
raise IndexError("Queue is empty")
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
return self.output_stack[-1]
def is_empty(self):
"""O(1) - Check if empty"""
return not self.input_stack and not self.output_stack
def size(self):
"""O(1) - Get size"""
return len(self.input_stack) + len(self.output_stack)
# Example usage:
# enqueue(1), enqueue(2), enqueue(3)
# input_stack: [1, 2, 3] ← top
# output_stack: []
#
# dequeue() triggers transfer:
# input_stack: []
# output_stack: [3, 2, 1] ← top
# returns 1
3.5 Expression Evaluation Implementation
Postfix (RPN) Evaluation:
def evaluate_postfix(expression):
"""
Evaluate postfix expression
Algorithm:
1. Scan left to right
2. If operand: push to stack
3. If operator: pop 2 operands, apply operator, push result
Time: O(n), Space: O(n)
"""
stack = []
operators = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: a / b,
'^': lambda a, b: a ** b
}
tokens = expression.split()
for token in tokens:
if token in operators:
# Pop two operands (note the order!)
if len(stack) < 2:
raise ValueError("Invalid expression")
b = stack.pop() # Second operand
a = stack.pop() # First operand
result = operators[token](a, b)
stack.append(result)
else:
# Operand: push to stack
stack.append(float(token))
if len(stack) != 1:
raise ValueError("Invalid expression")
return stack[0]
# Example:
# "3 4 + 2 *" → ((3 + 4) * 2) = 14
# Stack trace:
# [3] → [3,4] → [7] → [7,2] → [14]
Infix to Postfix Conversion:
def infix_to_postfix(expression):
"""
Convert infix to postfix using Shunting-yard algorithm
Time: O(n), Space: O(n)
"""
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
associativity = {'+': 'L', '-': 'L', '*': 'L', '/': 'L', '^': 'R'}
output = []
operator_stack = []
tokens = expression.split()
for token in tokens:
if token.isalnum():
# Operand: add to output
output.append(token)
elif token in precedence:
# Operator: pop higher/equal precedence operators
while (operator_stack and
operator_stack[-1] != '(' and
operator_stack[-1] in precedence):
top_op = operator_stack[-1]
# Check precedence and associativity
if (precedence[top_op] > precedence[token] or
(precedence[top_op] == precedence[token] and
associativity[token] == 'L')):
output.append(operator_stack.pop())
else:
break
operator_stack.append(token)
elif token == '(':
operator_stack.append(token)
elif token == ')':
# Pop until matching '('
while operator_stack and operator_stack[-1] != '(':
output.append(operator_stack.pop())
if not operator_stack:
raise ValueError("Mismatched parentheses")
operator_stack.pop() # Remove '('
# Pop remaining operators
while operator_stack:
if operator_stack[-1] in '()':
raise ValueError("Mismatched parentheses")
output.append(operator_stack.pop())
return ' '.join(output)
# Example:
# "A + B * C" → "A B C * +"
# "( A + B ) * C" → "A B + C *"
Infix Evaluation (Combined):
def evaluate_infix(expression):
"""
Evaluate infix expression directly using two stacks
One stack for operands, one for operators
"""
def apply_operator(operators, values):
"""Apply top operator to top two values"""
op = operators.pop()
b = values.pop()
a = values.pop()
if op == '+': values.append(a + b)
elif op == '-': values.append(a - b)
elif op == '*': values.append(a * b)
elif op == '/': values.append(a / b)
elif op == '^': values.append(a ** b)
def precedence(op):
if op in '+-': return 1
if op in '*/': return 2
if op == '^': return 3
return 0
values = [] # Operand stack
operators = [] # Operator stack
i = 0
while i < len(expression):
if expression[i] == ' ':
i += 1
continue
if expression[i] == '(':
operators.append(expression[i])
elif expression[i].isdigit():
# Parse multi-digit number
num = 0
while i < len(expression) and expression[i].isdigit():
num = num * 10 + int(expression[i])
i += 1
values.append(num)
i -= 1
elif expression[i] == ')':
while operators and operators[-1] != '(':
apply_operator(operators, values)
operators.pop() # Remove '('
else: # Operator
while (operators and operators[-1] != '(' and
precedence(operators[-1]) >= precedence(expression[i])):
apply_operator(operators, values)
operators.append(expression[i])
i += 1
while operators:
apply_operator(operators, values)
return values[0]
# Example: evaluate_infix("3 + 4 * 2") → 11
3.6 Balanced Parentheses Implementation
def is_balanced_parentheses(s):
"""
Check if parentheses/brackets are balanced
Time: O(n), Space: O(n)
"""
stack = []
matching = {'(': ')', '[': ']', '{': '}'}
for char in s:
if char in matching:
# Opening bracket: push to stack
stack.append(char)
elif char in matching.values():
# Closing bracket: check match
if not stack:
return False # No matching opening
if matching[stack[-1]] != char:
return False # Mismatch
stack.pop()
return len(stack) == 0 # All opened brackets should be closed
# Examples:
# "()" → True
# "()[]{}" → True
# "(]" → False
# "([)]" → False
# "{[]}" → True
def is_valid_expression(expression):
"""
Validate parentheses in mathematical expression
Ignores non-bracket characters
"""
stack = []
brackets = {'(': ')', '[': ']', '{': '}'}
for char in expression:
if char in brackets:
stack.append(char)
elif char in brackets.values():
if not stack or brackets[stack.pop()] != char:
return False
return not stack
# More detailed version with error reporting
def validate_parentheses_detailed(s):
"""
Returns (is_valid, error_message, error_position)
"""
stack = []
matching = {'(': ')', '[': ']', '{': '}'}
for i, char in enumerate(s):
if char in matching:
stack.append((char, i))
elif char in matching.values():
if not stack:
return (False, f"Unmatched closing bracket '{char}'", i)
opening, pos = stack.pop()
if matching[opening] != char:
return (False,
f"Mismatched brackets: '{opening}' at {pos} and '{char}' at {i}",
i)
if stack:
opening, pos = stack[0]
return (False, f"Unmatched opening bracket '{opening}'", pos)
return (True, "Valid", -1)
3.7 Next Greater Element Implementation
def next_greater_element(arr):
"""
Find next greater element for each element in array
Uses monotonic decreasing stack
Time: O(n), Space: O(n)
For each element, find the first greater element to its right
"""
n = len(arr)
result = [-1] * n # Default: no greater element
stack = [] # Stores indices
for i in range(n):
# Pop elements smaller than current
while stack and arr[stack[-1]] < arr[i]:
index = stack.pop()
result[index] = arr[i]
stack.append(i)
return result
# Example:
# Input: [4, 5, 2, 10, 8]
# Output: [5, 10, 10, -1, -1]
# Circular array variation
def next_greater_circular(arr):
"""
Next greater element in circular array
Trick: Process array twice but only fill result once
"""
n = len(arr)
result = [-1] * n
stack = []
# Process array twice for circular behavior
for i in range(2 * n):
actual_index = i % n
while stack and arr[stack[-1]] < arr[actual_index]:
index = stack.pop()
result[index] = arr[actual_index]
# Only add indices from first pass
if i < n:
stack.append(actual_index)
return result
# Previous greater element
def previous_greater_element(arr):
"""
Find previous greater element (scan left to right)
"""
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
while stack and arr[stack[-1]] <= arr[i]:
stack.pop()
if stack:
result[i] = arr[stack[-1]]
stack.append(i)
return result
# Next smaller element
def next_smaller_element(arr):
"""
Find next smaller element (reverse logic)
Uses monotonic increasing stack
"""
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
# Pop elements greater than or equal to current
while stack and arr[stack[-1]] > arr[i]:
index = stack.pop()
result[index] = arr[i]
stack.append(i)
return result
3.8 Stock Span Problem Implementation
def calculate_stock_span(prices):
"""
Calculate stock span for each day
Span: number of consecutive days before current day
where price <= current price
Time: O(n), Space: O(n)
"""
n = len(prices)
span = [1] * n # Minimum span is 1 (the day itself)
stack = [] # Stores indices
for i in range(n):
# Pop days with price <= current price
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
# Span = distance to previous greater element
if stack:
span[i] = i - stack[-1]
else:
span[i] = i + 1 # All previous days
stack.append(i)
return span
# Example:
# Prices: [100, 80, 60, 70, 60, 75, 85]
# Span: [1, 1, 1, 2, 1, 4, 6]
#
# Day 5 (price=75): includes days 5,4,3,2 (span=4)
# Day 6 (price=85): includes days 6,5,4,3,2,1 (span=6)
class StockSpanner:
"""
Online algorithm: calculate span as prices come
Useful for real-time processing
"""
def __init__(self):
self.stack = [] # Stores (price, span) pairs
self.index = -1
def next(self, price):
"""
Process next price and return its span
O(1) amortized
"""
self.index += 1
span = 1
# Merge with previous spans
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
# Usage:
# spanner = StockSpanner()
# spanner.next(100) → 1
# spanner.next(80) → 1
# spanner.next(60) → 1
# spanner.next(70) → 2
# spanner.next(60) → 1
# spanner.next(75) → 4
# spanner.next(85) → 6
3.9 Monotonic Stack Pattern Implementation
class MonotonicStack:
"""
Generic monotonic stack for various problems
"""
@staticmethod
def next_greater_element(arr):
"""NGE using monotonic decreasing stack"""
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
stack.append(i)
return result
@staticmethod
def largest_rectangle_histogram(heights):
"""
Largest rectangle in histogram
For each bar, find:
- Left boundary: previous smaller element
- Right boundary: next smaller element
- Area = height[i] * (right - left - 1)
"""
stack = []
max_area = 0
index = 0
while index < len(heights):
# If increasing, push
if not stack or heights[index] >= heights[stack[-1]]:
stack.append(index)
index += 1
else:
# Calculate area with popped height as smallest
top = stack.pop()
width = index if not stack else index - stack[-1] - 1
area = heights[top] * width
max_area = max(max_area, area)
# Process remaining bars
while stack:
top = stack.pop()
width = index if not stack else index - stack[-1] - 1
area = heights[top] * width
max_area = max(max_area, area)
return max_area
@staticmethod
def trapping_rain_water(height):
"""
Calculate trapped rain water using monotonic decreasing stack
"""
stack = []
water = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop()
if not stack:
break
distance = i - stack[-1] - 1
bounded_height = min(height[i], height[stack[-1]]) - height[bottom]
water += distance * bounded_height
stack.append(i)
return water
@staticmethod
def daily_temperatures(temperatures):
"""
Days until warmer temperature
Variation of next greater element
"""
n = len(temperatures)
result = [0] * n
stack = []
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result
3.10 Backtracking with Stack Implementation
def generate_parentheses_backtracking(n):
"""
Generate all valid parentheses combinations
Backtracking approach with explicit stack
"""
result = []
stack = [(0, 0, "")] # (open_count, close_count, current_string)
while stack:
open_count, close_count, current = stack.pop()
# Valid combination found
if len(current) == 2 * n:
result.append(current)
continue
# Add closing parenthesis (if valid)
if close_count < open_count:
stack.append((open_count, close_count + 1, current + ")"))
# Add opening parenthesis (if valid)
if open_count < n:
stack.append((open_count + 1, close_count, current + "("))
return result
def solve_maze_backtracking(maze, start, end):
"""
Solve maze using stack-based backtracking
maze: 2D grid (0=path, 1=wall)
"""
rows, cols = len(maze), len(maze[0])
visited = set()
stack = [(start, [start])] # (position, path)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # Right, Down, Left, Up
while stack:
(row, col), path = stack.pop()
if (row, col) == end:
return path # Solution found
if (row, col) in visited:
continue
visited.add((row, col))
# Explore neighbors
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# Check bounds and walls
if (0 <= new_row < rows and
0 <= new_col < cols and
maze[new_row][new_col] == 0 and
(new_row, new_col) not in visited):
stack.append(((new_row, new_col), path + [(new_row, new_col)]))
return None # No solution
def permutations_backtracking(nums):
"""
Generate all permutations using stack
"""
result = []
stack = [([], nums)] # (current_permutation, remaining_elements)
while stack:
current, remaining = stack.pop()
if not remaining:
result.append(current)
continue
for i in range(len(remaining)):
# Choose element at index i
new_current = current + [remaining[i]]
new_remaining = remaining[:i] + remaining[i+1:]
stack.append((new_current, new_remaining))
return result
def n_queens_stack(n):
"""
N-Queens problem using stack
Place n queens on n×n board such that no two queens attack each other
"""
def is_valid(board, row, col):
# Check column
for r in range(row):
if board[r] == col:
return False
# Check diagonals
for r in range(row):
if abs(board[r] - col) == abs(r - row):
return False
return True
solutions = []
stack = [(0, [])] # (row, board_configuration)
while stack:
row, board = stack.pop()
if row == n:
solutions.append(board[:])
continue
for col in range(n):
if is_valid(board, row, col):
stack.append((row + 1, board + [col]))
return solutions
def subset_sum_backtracking(nums, target):
"""
Find all subsets that sum to target
"""
result = []
stack = [(0, [], 0)] # (index, current_subset, current_sum)
while stack:
index, current, current_sum = stack.pop()
if current_sum == target:
result.append(current[:])
# Continue to find other solutions
if index >= len(nums) or current_sum > target:
continue
# Exclude current number
stack.append((index + 1, current, current_sum))
# Include current number
stack.append((index + 1, current + [nums[index]], current_sum + nums[index]))
return result
4. Problem-Solving and Applications
4.1 Expression Evaluation Problems
Problem 1: Basic Calculator
def basic_calculator(s):
"""
Evaluate expression with +, -, (, )
Example: "1 + 1" = 2
"(1+(4+5+2)-3)+(6+8)" = 23
Time: O(n), Space: O(n)
"""
stack = []
num = 0
sign = 1 # 1 for positive, -1 for negative
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 == '(':
# Push current result and sign
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ')':
result += sign * num
num = 0
result *= stack.pop() # Pop sign
result += stack.pop() # Pop previous result
result += sign * num
return result
Problem 2: Calculator with Multiplication and Division
def calculator_with_mult_div(s):
"""
Evaluate expression with +, -, *, /
Handle precedence without parentheses
"""
stack = []
num = 0
operation = '+'
for i, char in enumerate(s):
if char.isdigit():
num = num * 10 + int(char)
if char in '+-*/' or i == len(s) - 1:
if operation == '+':
stack.append(num)
elif operation == '-':
stack.append(-num)
elif operation == '*':
stack.append(stack.pop() * num)
elif operation == '/':
stack.append(int(stack.pop() / num)) # Truncate towards zero
if char in '+-*/':
operation = char
num = 0
return sum(stack)
# Example: "3+2*2" = 7
# Stack trace: [3] → [3, 2] → [3, 4] → sum=7
Problem 3: Reverse Polish Notation Calculator
def eval_rpn(tokens):
"""
Evaluate Reverse Polish Notation
Example: ["2", "1", "+", "3", "*"] = ((2 + 1) * 3) = 9
"""
stack = []
for token in tokens:
if token in '+-*/':
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
4.2 Parentheses Problems
Problem 1: Minimum Add to Make Valid
def min_add_to_make_valid(s):
"""
Minimum insertions to make parentheses valid
Example: "())" → 1 (need one '(')
"(((" → 3 (need three ')')
"""
open_needed = 0 # Unmatched '('
close_needed = 0 # Need ')'
for char in s:
if char == '(':
close_needed += 1
elif char == ')':
if close_needed > 0:
close_needed -= 1
else:
open_needed += 1
return open_needed + close_needed
# Stack-based alternative
def min_add_stack(s):
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if stack and stack[-1] == '(':
stack.pop()
else:
stack.append(char)
return len(stack)
Problem 2: Remove Invalid Parentheses
def remove_invalid_parentheses(s):
"""
Remove minimum invalid parentheses to make valid
Return all possible results
"""
def is_valid(s):
count = 0
for char in s:
if char == '(': count += 1
elif char == ')': count -= 1
if count < 0: return False
return count == 0
# BFS to find minimum removals
from collections import deque
visited = {s}
queue = deque([s])
result = []
found = False
while queue:
current = queue.popleft()
if is_valid(current):
result.append(current)
found = True
if found:
continue
# Try removing each parenthesis
for i in range(len(current)):
if current[i] not in '()':
continue
next_s = current[:i] + current[i+1:]
if next_s not in visited:
visited.add(next_s)
queue.append(next_s)
return result
Problem 3: Longest Valid Parentheses
def longest_valid_parentheses(s):
"""
Find length of longest valid substring
Example: "(()" → 2
")()())" → 4
Time: O(n), Space: O(n)
"""
stack = [-1] # Base index
max_length = 0
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i) # New base
else:
max_length = max(max_length, i - stack[-1])
return max_length
# Two-pass O(1) space solution
def longest_valid_two_pass(s):
max_length = 0
left = right = 0
# Left to right
for char in s:
if char == '(': left += 1
else: right += 1
if left == right:
max_length = max(max_length, 2 * right)
elif right > left:
left = right = 0
# Right to left
left = right = 0
for char in reversed(s):
if char == '(': left += 1
else: right += 1
if left == right:
max_length = max(max_length, 2 * left)
elif left > right:
left = right = 0
return max_length
4.3 Next Greater Element Variations
Problem 1: Next Greater Element II (Circular)
def next_greater_elements_circular(nums):
"""
Next greater element in circular array
Example: [1,2,1] → [2,-1,2]
"""
n = len(nums)
result = [-1] * n
stack = []
# Traverse twice
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
result[stack.pop()] = nums[i % n]
if i < n:
stack.append(i)
return result
Problem 2: Buildings With Ocean View
def find_buildings_with_ocean_view(heights):
"""
Find buildings that can see ocean (on the right)
A building can see ocean if all buildings to its right are shorter
Example: [4,2,3,1] → [0,2,3]
"""
stack = []
for i in range(len(heights)):
# Remove buildings blocked by current
while stack and heights[stack[-1]] <= heights[i]:
stack.pop()
stack.append(i)
return stack
# Right to left approach (simpler)
def buildings_ocean_view_rtl(heights):
result = []
max_height = 0
for i in range(len(heights) - 1, -1, -1):
if heights[i] > max_height:
result.append(i)
max_height = heights[i]
return result[::-1]
Problem 3: Sum of Subarray Minimums
def sum_subarray_minimums(arr):
"""
Sum of minimum of all subarrays
Use monotonic increasing stack to find:
- Previous less element (PLE)
- Next less element (NLE)
For each element, count subarrays where it's minimum
"""
MOD = 10**9 + 7
n = len(arr)
# Find previous less element
prev_less = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
prev_less[i] = stack[-1] if stack else -1
stack.append(i)
# Find next less element
next_less = [n] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
next_less[stack.pop()] = i
stack.append(i)
# Calculate contribution of each element
result = 0
for i in range(n):
left = i - prev_less[i]
right = next_less[i] - i
result = (result + arr[i] * left * right) % MOD
return result
4.4 Stack-Based Tree Traversal
Problem: Iterative Tree Traversals
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_iterative(root):
"""
Inorder traversal: Left → Root → Right
"""
result = []
stack = []
current = root
while current or stack:
# Go to leftmost node
while current:
stack.append(current)
current = current.left
# Process node
current = stack.pop()
result.append(current.val)
# Visit right subtree
current = current.right
return result
def preorder_iterative(root):
"""
Preorder traversal: Root → Left → Right
"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push right first (will be processed after left)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
def postorder_iterative(root):
"""
Postorder traversal: Left → Right → Root
Trick: Reverse of Root → Right → Left
"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push left first (opposite of preorder)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1] # Reverse
4.5 Histogram and Rectangle Problems
Problem 1: Largest Rectangle in Histogram
def largest_rectangle_area(heights):
"""
Find largest rectangle in histogram
For each bar, find how far it can extend left and right
Use monotonic increasing stack
Time: O(n), Space: O(n)
"""
stack = []
max_area = 0
index = 0
while index < len(heights):
# If current bar is higher, push
if not stack or heights[index] >= heights[stack[-1]]:
stack.append(index)
index += 1
else:
# Pop and calculate area
top = stack.pop()
# Width calculation
width = index if not stack else index - stack[-1] - 1
area = heights[top] * width
max_area = max(max_area, area)
# Process remaining bars
while stack:
top = stack.pop()
width = index if not stack else index - stack[-1] - 1
area = heights[top] * width
max_area = max(max_area, area)
return max_area
# Example: [2,1,5,6,2,3] → 10
# The rectangle is formed by heights [5,6] with width 2
Problem 2: Maximal Rectangle
def maximal_rectangle(matrix):
"""
Largest rectangle of 1's in binary matrix
Treat each row as base of histogram
"""
if not matrix:
return 0
max_area = 0
heights = [0] * len(matrix[0])
for row in matrix:
# Update heights
for i in range(len(row)):
heights[i] = heights[i] + 1 if row[i] == '1' else 0
# Find max rectangle in current histogram
max_area = max(max_area, largest_rectangle_area(heights))
return max_area
4.6 String Manipulation with Stacks
Problem 1: Remove K Digits
def remove_k_digits(num, k):
"""
Remove k digits to make smallest number
Use monotonic increasing stack
"""
stack = []
for digit in num:
# Remove larger digits from stack
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# Remove remaining k digits from end
stack = stack[:-k] if k > 0 else stack
# Convert to string and remove leading zeros
result = ''.join(stack).lstrip('0')
return result if result else '0'
# Example: num="1432219", k=3 → "1219"
Problem 2: Decode String
def decode_string(s):
"""
Decode encoded string
Example: "3[a]2[bc]" → "aaabcbc"
"3[a2[c]]" → "accaccacc"
"""
stack = []
current_num = 0
current_string = ""
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
# Push current state to stack
stack.append((current_string, current_num))
current_string = ""
current_num = 0
elif char == ']':
# Pop and decode
prev_string, num = stack.pop()
current_string = prev_string + current_string * num
else:
current_string += char
return current_string
Problem 3: Simplify Path
def simplify_path(path):
"""
Simplify Unix file path
Example: "/home/" → "/home"
"/a/./b/../../c/" → "/c"
"""
stack = []
components = path.split('/')
for component in components:
if component == '..':
if stack:
stack.pop()
elif component and component != '.':
stack.append(component)
return '/' + '/'.join(stack)
4.7 Backtracking Applications
Problem 1: Generate All Balanced Parentheses
def generate_parentheses(n):
"""
Generate all valid combinations of n pairs of parentheses
Example: n=3 → ["((()))","(()())","(())()","()(())","()()()"]
"""
result = []
def backtrack(current, open_count, close_count):
if len(current) == 2 * n:
result.append(current)
return
if open_count < n:
backtrack(current + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(current + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
# Iterative with stack
def generate_parentheses_stack(n):
result = []
stack = [('', 0, 0)]
while stack:
current, open_count, close_count = stack.pop()
if len(current) == 2 * n:
result.append(current)
continue
if close_count < open_count:
stack.append((current + ')', open_count, close_count + 1))
if open_count < n:
stack.append((current + '(', open_count + 1, close_count))
return result
Problem 2: Letter Combinations of Phone Number
def letter_combinations(digits):
"""
Generate all letter combinations from phone number
Example: "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]
"""
if not digits:
return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi',
'5': 'jkl', '6': 'mno', '7': 'pqrs',
'8': 'tuv', '9': 'wxyz'
}
result = []
stack = [('', 0)] # (current_combination, index)
while stack:
combination, index = stack.pop()
if index == len(digits):
result.append(combination)
continue
for letter in phone[digits[index]]:
stack.append((combination + letter, index + 1))
return result
5. Complexity Analysis
5.1 Time Complexity Analysis
Basic Stack Operations:
| Operation | Array-Based | Linked List | Explanation | | --------- | ----------- | ----------- | ----------------------------- | | push() | O(1)* | O(1) | *Amortized for dynamic array | | pop() | O(1) | O(1) | Always constant time | | peek() | O(1) | O(1) | Direct access to top | | isEmpty() | O(1) | O(1) | Check top pointer | | size() | O(1) | O(1) | Cached value |
Amortized Analysis for Dynamic Array:
def analyze_dynamic_array_push():
"""
Push operation amortized analysis
When array is full, double capacity:
- Cost of n pushes with doubling: n + (1+2+4+8+...+n)
- Geometric series sum: 2n
- Amortized cost per push: 2n/n = O(1)
"""
costs = []
capacity = 1
size = 0
for i in range(1, 33):
if size == capacity:
# Resize: copy all elements
cost = capacity
capacity *= 2
else:
cost = 1
costs.append(cost)
size += 1
print(f"Total cost: {sum(costs)}")
print(f"Average cost: {sum(costs)/len(costs):.2f}")
# Output: Average cost ≈ 2 (amortized O(1))
Algorithm Complexities:
def complexity_analysis():
"""Analysis of stack-based algorithms"""
analyses = {
"Balanced Parentheses": {
"time": "O(n)",
"space": "O(n)",
"explanation": "Single pass, max stack size = n/2 for all '('"
},
"Expression Evaluation": {
"infix_to_postfix": {
"time": "O(n)",
"space": "O(n)",
"explanation": "Each token processed once"
},
"evaluate_postfix": {
"time": "O(n)",
"space": "O(n)",
"explanation": "Each token processed once, max n/2 operands"
}
},
"Next Greater Element": {
"time": "O(n)",
"space": "O(n)",
"explanation": "Each element pushed/popped once"
},
"Stock Span": {
"time": "O(n)",
"space": "O(n)",
"explanation": "Amortized O(1) per element"
},
"Largest Rectangle Histogram": {
"time": "O(n)",
"space": "O(n)",
"explanation": "Each bar pushed/popped once"
},
"Min Stack": {
"push": "O(1)",
"pop": "O(1)",
"getMin": "O(1)",
"space": "O(n)",
"explanation": "Auxiliary min stack"
},
"Queue Using Stacks": {
"enqueue": "O(1)",
"dequeue": "O(1) amortized",
"space": "O(n)",
"explanation": "Each element moved at most twice"
}
}
return analyses
Monotonic Stack Analysis:
def monotonic_stack_complexity_proof():
"""
Proof that monotonic stack is O(n)
Key insight: Each element is pushed and popped at most once
"""
proof = """
Monotonic Stack Time Complexity Proof:
Consider array of n elements.
Loop iterations: n (one per element)
Total push operations:
- Each element pushed exactly once
- Total pushes = n
Total pop operations:
- Each element popped at most once
- Total pops ≤ n
Work per iteration:
- While loop pops: amortized O(1)
- Single push: O(1)
- Total per iteration: amortized O(1)
Total time complexity:
- n iterations × O(1) = O(n)
Therefore: O(n) time complexity
"""
return proof
5.2 Space Complexity Analysis
Stack Space Usage:
def space_complexity_examples():
"""Space complexity for various stack operations"""
examples = {
"Basic Stack": {
"space": "O(n)",
"description": "Store n elements"
},
"Min Stack (Two Stacks)": {
"space": "O(n)",
"description": "Main stack O(n) + min stack O(n)"
},
"Min Stack (Optimized)": {
"space": "O(n)",
"description": "Best case O(1) if all same, worst case O(n)"
},
"Expression Evaluation": {
"space": "O(n)",
"description": "Operator stack + operand stack"
},
"Next Greater Element": {
"space": "O(n)",
"description": "Stack + result array"
},
"Recursive DFS": {
"implicit_stack": "O(h)",
"description": "h = height of recursion tree"
},
"Iterative DFS": {
"explicit_stack": "O(w)",
"description": "w = maximum width of tree"
}
}
return examples
Auxiliary Space Analysis:
class SpaceOptimizedStack:
"""Demonstration of space optimization techniques"""
def __init__(self):
self.data = []
def push_with_min_optimized(self, val):
"""
Store only differences from minimum
Saves space when numbers are close to min
"""
if not self.data:
self.data.append((val, val))
else:
current_min = self.data[-1][1]
self.data.append((val - current_min, min(val, current_min)))
def analyze_space_saving(self, values):
"""
Compare space usage of different approaches
"""
# Approach 1: Two stacks
main_stack = values
min_stack = values # Worst case: all elements
space_two_stacks = len(main_stack) + len(min_stack)
# Approach 2: Optimized (only store when min changes)
space_optimized = len(values) + len(set(values)) # Approximation
# Approach 3: Single stack with tuples
space_tuples = len(values) * 2 # (value, min) pairs
return {
"two_stacks": space_two_stacks,
"optimized": space_optimized,
"tuples": space_tuples
}
5.3 Comparison with Other Data Structures
Time Complexity Comparison:
def compare_data_structures():
"""
Compare stack operations with other structures
"""
comparison = {
"Operation": ["Insert", "Delete", "Search", "Access nth", "Min/Max"],
"Stack": {
"Insert": "O(1)",
"Delete": "O(1)",
"Search": "O(n)",
"Access nth": "O(n)",
"Min/Max": "O(n) or O(1)*"
},
"Queue": {
"Insert": "O(1)",
"Delete": "O(1)",
"Search": "O(n)",
"Access nth": "O(n)",
"Min/Max": "O(n)"
},
"Array": {
"Insert": "O(n)",
"Delete": "O(n)",
"Search": "O(n) or O(log n)**",
"Access nth": "O(1)",
"Min/Max": "O(n) or O(1)***"
},
"Linked List": {
"Insert": "O(1)****",
"Delete": "O(1)****",
"Search": "O(n)",
"Access nth": "O(n)",
"Min/Max": "O(n)"
},
"Heap": {
"Insert": "O(log n)",
"Delete": "O(log n)",
"Search": "O(n)",
"Access nth": "O(n)",
"Min/Max": "O(1)"
}
}
notes = """
* With Min Stack design
** Binary search if sorted
*** If maintaining sorted order
**** With pointer to node
"""
return comparison, notes
5.4 Worst-Case vs Average-Case Analysis
def worst_vs_average_case():
"""
Analyze worst and average cases for stack operations
"""
analysis = {
"Dynamic Array Push": {
"worst_case": "O(n)",
"average_case": "O(1)",
"amortized": "O(1)",
"explanation": """
Worst case: When array is full, must copy all n elements
Average case: Most pushes are O(1), occasional O(n) resize
Amortized: Total cost of n operations / n = O(1)
"""
},
"Next Greater Element": {
"worst_case": "O(n)",
"best_case": "O(n)",
"average_case": "O(n)",
"explanation": """
Always O(n): Each element pushed and popped exactly once
Independent of input distribution
"""
},
"Queue Using Stacks": {
"enqueue": {
"worst": "O(1)",
"average": "O(1)"
},
"dequeue": {
"worst": "O(n)",
"average": "O(1)",
"amortized": "O(1)"
},
"explanation": """
Dequeue worst case: Transfer all n elements from input to output
Amortized: Each element moved at most twice (input→output→result)
"""
},
"Expression Evaluation": {
"worst_case": "O(n)",
"best_case": "O(n)",
"explanation": """
Must process every token regardless of expression structure
"""
}
}
return analysis
5.5 Benchmark Results
import time
import random
def benchmark_stack_implementations():
"""
Benchmark different stack implementations
"""
def benchmark_push_pop(stack_impl, n):
"""Measure push/pop performance"""
start = time.time()
# Push n elements
for i in range(n):
stack_impl.push(i)
# Pop n elements
for i in range(n):
stack_impl.pop()
return time.time() - start
results = {}
sizes = [1000, 10000, 100000]
for size in sizes:
# Array-based stack (Python list)
array_stack = DynamicArrayStack()
array_time = benchmark_push_pop(array_stack, size)
# Linked list stack
linked_stack = LinkedStack()
linked_time = benchmark_push_pop(linked_stack, size)
results[size] = {
"array_based": array_time,
"linked_list": linked_time,
"ratio": linked_time / array_time if array_time > 0 else 0
}
return results
# Typical results (approximate):
# Size: 1000 - Array: 0.0001s, Linked: 0.0003s (3x slower)
# Size: 10000 - Array: 0.001s, Linked: 0.003s (3x slower)
# Size: 100000 - Array: 0.01s, Linked: 0.03s (3x slower)
#
# Conclusion: Array-based is faster due to cache locality
6. Optimization and Trade-offs
6.1 Array vs Linked List Implementation
Trade-off Analysis:
class StackImplementationComparison:
"""
Detailed comparison of stack implementations
"""
@staticmethod
def array_based_pros_cons():
return {
"Pros": [
"Better cache locality (contiguous memory)",
"Faster access due to CPU cache",
"Less memory overhead (no pointers)",
"Simple implementation",
"Better for small, known-size stacks"
],
"Cons": [
"Fixed size (for static arrays)",
"Resizing cost (for dynamic arrays)",
"Wasted space if underutilized",
"Occasional O(n) push operation"
]
}
@staticmethod
def linked_list_pros_cons():
return {
"Pros": [
"Dynamic size (no resize needed)",
"Consistent O(1) operations",
"No wasted space",
"Good for unpredictable sizes"
],
"Cons": [
"Extra memory for pointers",
"Poor cache locality",
"Slower due to pointer dereferencing",
"Memory fragmentation"
]
}
@staticmethod
def when_to_use_each():
return {
"Use Array-Based When": [
"Size is known or bounded",
"Performance is critical",
"Stack is frequently accessed",
"Memory is not highly fragmented",
"Working with primitive types"
],
"Use Linked List When": [
"Size is highly variable",
"Consistent performance required",
"Memory is highly fragmented",
"Avoiding resize overhead is critical",
"Stack size is unpredictable"
]
}
Hybrid Approach:
class HybridStack:
"""
Combines benefits of both implementations
Use array for small stacks, switch to linked list for large ones
"""
def __init__(self, threshold=1000):
self.threshold = threshold
self.array_stack = []
self.overflow_stack = None # Linked list for overflow
self.size = 0
def push(self, item):
"""Switch to linked list after threshold"""
if self.size < self.threshold:
self.array_stack.append(item)
else:
if not self.overflow_stack:
self.overflow_stack = LinkedStack()
self.overflow_stack.push(item)
self.size += 1
def pop(self):
"""Pop from appropriate structure"""
if self.size == 0:
raise IndexError("Stack is empty")
if self.overflow_stack and not self.overflow_stack.is_empty():
self.size -= 1
return self.overflow_stack.pop()
else:
self.size -= 1
return self.array_stack.pop()
def peek(self):
if self.overflow_stack and not self.overflow_stack.is_empty():
return self.overflow_stack.peek()
return self.array_stack[-1] if self.array_stack else None
6.2 Space Optimization Techniques
Min Stack Space Optimization:
class MinStackSpaceOptimized:
"""
Optimize space for Min Stack
Only store differences and track minimum
"""
def __init__(self):
self.stack = []
self.min_val = None
def push(self, val):
if not self.stack:
self.stack.append(0)
self.min_val = val
else:
# Store difference from minimum
diff = val - self.min_val
self.stack.append(diff)
# Update minimum if needed
if val < self.min_val:
self.min_val = val
def pop(self):
if not self.stack:
raise IndexError("Stack is empty")
diff = self.stack.pop()
if diff < 0:
# Current min was the popped value
# Restore previous min
popped = self.min_val
self.min_val = self.min_val - diff
return popped
else:
return self.min_val + diff
def top(self):
if not self.stack:
raise IndexError("Stack is empty")
diff = self.stack[-1]
return self.min_val if diff < 0 else self.min_val + diff
def getMin(self):
return self.min_val
# Space complexity: O(n) for stack only (no auxiliary structure)
Bit Manipulation for Boolean Stacks:
class CompactBooleanStack:
"""
Store boolean values compactly using bits
Each integer stores 32/64 boolean values
"""
def __init__(self):
self.data = []
self.size = 0
self.bits_per_int = 32
def push(self, value):
"""Push boolean value"""
if self.size % self.bits_per_int == 0:
self.data.append(0)
if value:
# Set bit
word_index = self.size // self.bits_per_int
bit_index = self.size % self.bits_per_int
self.data[word_index] |= (1 << bit_index)
self.size += 1
def pop(self):
"""Pop boolean value"""
if self.size == 0:
raise IndexError("Stack is empty")
self.size -= 1
word_index = self.size // self.bits_per_int
bit_index = self.size % self.bits_per_int
value = bool(self.data[word_index] & (1 << bit_index))
# Remove word if empty
if self.size % self.bits_per_int == 0:
self.data.pop()
return value
# Space savings: 32x or 64x for boolean values
6.3 Performance Optimization
Cache-Friendly Stack Layout:
class CacheFriendlyStack:
"""
Optimize for CPU cache performance
Keep frequently accessed data together
"""
def __init__(self, capacity=64):
# Allocate in powers of 2 for cache alignment
self.capacity = capacity
self.data = [None] * capacity
self.top_index = -1
# Keep metadata together
self.stats = {
'pushes': 0,
'pops': 0,
'peak_size': 0
}
def push(self, item):
if self.top_index + 1 >= self.capacity:
# Double capacity (power of 2)
new_capacity = self.capacity * 2
new_data = [None] * new_capacity
new_data[:self.capacity] = self.data
self.data = new_data
self.capacity = new_capacity
self.top_index += 1
self.data[self.top_index] = item
# Update stats
self.stats['pushes'] += 1
self.stats['peak_size'] = max(self.stats['peak_size'], self.top_index + 1)
def pop(self):
if self.top_index < 0:
raise IndexError("Stack is empty")
item = self.data[self.top_index]
self.data[self.top_index] = None
self.top_index -= 1
self.stats['pops'] += 1
# Shrink if using < 1/4 capacity
if self.top_index < self.capacity // 4 and self.capacity > 64:
self.capacity //= 2
self.data = self.data[:self.capacity]
return item
Lazy Evaluation for Expression Stacks:
class LazyExpressionStack:
"""
Defer computation until result is needed
Useful for complex expressions with short-circuit evaluation
"""
def __init__(self):
self.stack = []
def push_value(self, value):
"""Push concrete value"""
self.stack.append(('value', value))
def push_operation(self, op, lazy=True):
"""Push operation (optionally lazy)"""
if lazy:
self.stack.append(('op', op))
else:
self.evaluate_top()
def evaluate_top(self):
"""Evaluate top operation"""
if len(self.stack) < 3:
return
if self.stack[-2][0] == 'op':
op = self.stack.pop()[1]
b = self.stack.pop()[1]
a = self.stack.pop()[1]
result = self.apply_op(a, b, op)
self.stack.append(('value', result))
def apply_op(self, a, b, op):
"""Apply binary operation"""
if op == '+': return a + b
elif op == '-': return a - b
elif op == '*': return a * b
elif op == '/': return a / b
def get_result(self):
"""Force evaluation and get result"""
while len(self.stack) > 1:
self.evaluate_top()
return self.stack[0][1] if self.stack else None
6.4 Memory Management Trade-offs
Pre-allocation vs Dynamic Growth:
class PreAllocatedStack:
"""
Pre-allocate large capacity to avoid resizing
Trade: Memory for speed
"""
def __init__(self, expected_max_size=10000):
self.data = [None] * expected_max_size
self.capacity = expected_max_size
self.top_index = -1
def push(self, item):
"""No resize overhead"""
if self.top_index + 1 >= self.capacity:
raise OverflowError("Stack capacity exceeded")
self.top_index += 1
self.data[self.top_index] = item
# Pros: Consistent O(1) push, no resize cost
# Cons: Wasted memory if overestimated
class ConservativeStack:
"""
Start small, grow conservatively
Trade: Speed for memory efficiency
"""
def __init__(self, initial_capacity=4):
self.data = [None] * initial_capacity
self.capacity = initial_capacity
self.top_index = -1
def push(self, item):
"""Grow by fixed amount instead of doubling"""
if self.top_index + 1 >= self.capacity:
# Grow by 50% instead of 100%
new_capacity = self.capacity + self.capacity // 2
self.resize(new_capacity)
self.top_index += 1
self.data[self.top_index] = item
def resize(self, new_capacity):
new_data = [None] * new_capacity
new_data[:self.top_index + 1] = self.data[:self.top_index + 1]
self.data = new_data
self.capacity = new_capacity
# Pros: Less wasted memory
# Cons: More frequent resizes, slightly slower
6.5 Algorithm-Specific Optimizations
Optimized Next Greater Element:
def next_greater_optimized(arr):
"""
Optimizations for next greater element:
1. Early termination if array is sorted
2. Skip equal elements
3. Use indices only (reduce memory)
"""
n = len(arr)
# Check if sorted decreasing (quick exit)
if all(arr[i] >= arr[i+1] for i in range(n-1)):
return [-1] * n
result = [-1] * n
stack = []
for i in range(n):
# Skip duplicates at top
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
stack.append(i)
return result
def next_greater_early_exit(arr):
"""
Additional optimization: Exit early if stack empty
"""
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
stack.append(i)
# Early exit if found all NGEs
if not stack and i < len(arr) - 1:
# All previous elements have NGE
# Continue for remaining
pass
return result
Optimized Balanced Parentheses:
def is_balanced_optimized(s):
"""
Optimizations:
1. Early exit on odd length
2. Counter instead of stack for single type
3. Quick check for impossible cases
"""
# Quick checks
if len(s) % 2 != 0:
return False
if not s:
return True
# Check if single bracket type
bracket_types = set(s) & set('()[]{}<>')
if len(bracket_types) == 2: # Only one type (e.g., '(' and ')')
return s.count('(') == s.count(')')
# General case with stack
stack = []
matching = {'(': ')', '[': ']', '{': '}'}
for char in s:
if char in matching:
stack.append(char)
elif char in matching.values():
if not stack or matching[stack.pop()] != char:
return False
# Early exit if clearly unbalanced
if len(stack) > len(s) // 2:
return False
return not stack
7. Comparative Analysis
7.1 Stack vs Queue
Fundamental Differences:
class StackVsQueueComparison:
"""
Compare stack and queue characteristics
"""
@staticmethod
def get_comparison():
return {
"Ordering Principle": {
"Stack": "LIFO (Last-In-First-Out)",
"Queue": "FIFO (First-In-First-Out)"
},
"Primary Operations": {
"Stack": "push (add to top), pop (remove from top)",
"Queue": "enqueue (add to rear), dequeue (remove from front)"
},
"Access Pattern": {
"Stack": "Most recent element first",
"Queue": "Oldest element first"
},
"Use Cases": {
"Stack": [
"Function call management",
"Expression evaluation",
"Undo operations",
"DFS traversal",
"Backtracking"
],
"Queue": [
"Task scheduling",
"BFS traversal",
"Request handling",
"Print spooling",
"Message buffering"
]
},
"Real-World Analogy": {
"Stack": "Stack of plates (top access only)",
"Queue": "Line at ticket counter (front and rear)"
}
}
# Implementing Queue using Stacks demonstrates the relationship
def demonstrate_relationship():
"""
Stack and queue are dual structures
Two stacks can simulate a queue
"""
# Queue using two stacks
class QueueWith2Stacks:
def __init__(self):
self.input = [] # For enqueue
self.output = [] # For dequeue
def enqueue(self, x):
self.input.append(x)
def dequeue(self):
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output.pop() if self.output else None
# Stack using two queues (for comparison)
from collections import deque
class StackWith2Queues:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x):
self.q1.append(x)
def pop(self):
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
result = self.q1.popleft() if self.q1 else None
self.q1, self.q2 = self.q2, self.q1
return result
7.2 Stack vs Array/List
When to Choose Stack Over Array:
def stack_vs_array_decision():
"""
Decision framework for stack vs array
"""
return {
"Use Stack When": {
"reasons": [
"Only need access to most recent element",
"LIFO ordering is natural for problem",
"Implementing recursion iteratively",
"Tracking nested structures (parentheses)",
"Managing state in backtracking"
],
"examples": [
"Function call stack",
"Browser back button",
"Expression evaluation",
"DFS traversal"
]
},
"Use Array/List When": {
"reasons": [
"Need random access to elements",
"Require indexing operations",
"Need to access/modify middle elements",
"Want to sort or search efficiently",
"Storing collection without access restrictions"
],
"examples": [
"Student records",
"Game scores",
"Shopping cart items",
"Image pixels"
]
},
"Stack Advantages": [
"Enforces access discipline",
"Prevents accidental modification",
"Clear semantic meaning",
"Simplified interface reduces errors"
],
"Array Advantages": [
"Flexible access patterns",
"O(1) random access",
"Can sort and binary search",
"More operations available"
]
}
# Example: Stack is better for expression parsing
def why_stack_for_expressions():
"""
Array would work but stack is more natural
"""
# With array (awkward)
def evaluate_postfix_array(expression):
operands = []
for token in expression.split():
if token.isdigit():
operands.append(int(token)) # Use as stack
else:
b = operands.pop() # Still using stack operations!
a = operands.pop()
# Array features (indexing, slicing) not useful here
if token == '+': operands.append(a + b)
# With stack (natural)
def evaluate_postfix_stack(expression):
stack = []
for token in expression.split():
if token.isdigit():
stack.append(int(token))
else:
b, a = stack.pop(), stack.pop()
if token == '+': stack.append(a + b)
# Stack interface matches the problem domain
7.3 Stack vs Recursion
Stack as Recursion Simulation:
class RecursionVsStack:
"""
Every recursive algorithm can be converted to iterative with stack
"""
@staticmethod
def factorial_recursive(n):
"""Recursive approach"""
if n <= 1:
return 1
return n * RecursionVsStack.factorial_recursive(n - 1)
@staticmethod
def factorial_iterative_stack(n):
"""Iterative with explicit stack"""
stack = []
# Push all function calls
for i in range(n, 0, -1):
stack.append(i)
result = 1
while stack:
result *= stack.pop()
return result
@staticmethod
def fibonacci_recursive(n):
"""Recursive Fibonacci"""
if n <= 1:
return n
return (RecursionVsStack.fibonacci_recursive(n-1) +
RecursionVsStack.fibonacci_recursive(n-2))
@staticmethod
def fibonacci_iterative_stack(n):
"""Iterative Fibonacci with stack"""
if n <= 1:
return n
stack = [(n, None)] # (input, result)
computed = {}
while stack:
num, result = stack.pop()
if result is not None:
# Combining results
computed[num] = result
elif num in computed:
continue
elif num <= 1:
computed[num] = num
else:
# Push computation
stack.append((num, None))
# Push dependencies (reversed order)
if num - 1 not in computed:
stack.append((num - 1, None))
if num - 2 not in computed:
stack.append((num - 2, None))
return computed[n]
@staticmethod
def comparison():
return {
"Recursion": {
"Pros": [
"More readable for naturally recursive problems",
"Shorter code",
"Matches mathematical definitions",
"Automatic state management"
],
"Cons": [
"Stack overflow risk",
"Function call overhead",
"Limited stack depth (~1000 in Python)",
"Harder to debug"
]
},
"Explicit Stack": {
"Pros": [
"No recursion depth limit",
"Full control over stack",
"Can handle larger inputs",
"Easier to optimize"
],
"Cons": [
"More verbose",
"Manual state management",
"Less intuitive for some problems",
"More complex code"
]
}
}
Tree Traversal Comparison:
def tree_traversal_comparison():
"""
Compare recursive and stack-based tree traversal
"""
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Recursive DFS
def dfs_recursive(root, result=None):
if result is None:
result = []
if root:
result.append(root.val)
dfs_recursive(root.left, result)
dfs_recursive(root.right, result)
return result
# Iterative DFS with stack
def dfs_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push right first (will be processed after left)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
comparison = {
"Space Complexity": {
"Recursive": "O(h) implicit call stack",
"Iterative": "O(w) explicit stack (w = max width)"
},
"Flexibility": {
"Recursive": "Limited by language recursion depth",
"Iterative": "Can handle arbitrary depth"
},
"Code Clarity": {
"Recursive": "Clearer for tree problems",
"Iterative": "More verbose but explicit"
}
}
return comparison
7.4 Different Stack Applications Comparison
def compare_stack_applications():
"""
Compare different stack-based solutions
"""
comparison = {
"Expression Evaluation": {
"Problem Type": "Parsing",
"Stack Usage": "Operator precedence management",
"Why Stack": "Natural for nested operations",
"Alternatives": "Recursive descent parser",
"Stack Advantage": "Simpler, no recursion overhead"
},
"Balanced Parentheses": {
"Problem Type": "Matching",
"Stack Usage": "Track opening brackets",
"Why Stack": "LIFO matches nesting",
"Alternatives": "Counter (for single type)",
"Stack Advantage": "Handles multiple bracket types"
},
"Next Greater Element": {
"Problem Type": "Range queries",
"Stack Usage": "Monotonic stack",
"Why Stack": "Amortized O(1) per element",
"Alternatives": "Brute force O(n²)",
"Stack Advantage": "Linear time complexity"
},
"DFS Traversal": {
"Problem Type": "Graph/Tree traversal",
"Stack Usage": "Store nodes to visit",
"Why Stack": "Depth-first exploration",
"Alternatives": "Recursion",
"Stack Advantage": "Avoid recursion depth limit"
},
"Backtracking": {
"Problem Type": "State space exploration",
"Stack Usage": "Store decision points",
"Why Stack": "Undo last decision",
"Alternatives": "Recursion with parameter passing",
"Stack Advantage": "Explicit state management"
},
"Min/Max Stack": {
"Problem Type": "Augmented data structure",
"Stack Usage": "Track extrema efficiently",
"Why Stack": "Can maintain O(1) getMin",
"Alternatives": "Heap + stack",
"Stack Advantage": "Simpler, same complexity"
}
}
return comparison
7.5 Stack vs Other Data Structures for Specific Problems
Problem-Specific Comparisons:
def problem_specific_comparisons():
"""
Analyze which data structure is best for specific problems
"""
problems = {
"Undo/Redo": {
"Stack": {
"rating": "⭐⭐⭐⭐⭐",
"approach": "Two stacks (undo + redo)",
"complexity": "O(1) per operation",
"pros": "Natural fit, simple implementation"
},
"Array": {
"rating": "⭐⭐⭐",
"approach": "Array + index pointer",
"complexity": "O(1) per operation",
"pros": "Can view history"
},
"LinkedList": {
"rating": "⭐⭐",
"approach": "Doubly linked list",
"complexity": "O(1) per operation",
"pros": "Bidirectional navigation"
}
},
"Expression Parsing": {
"Stack": {
"rating": "⭐⭐⭐⭐⭐",
"approach": "Operator + operand stacks",
"complexity": "O(n)",
"pros": "Handles precedence naturally"
},
"Tree": {
"rating": "⭐⭐⭐⭐",
"approach": "Build expression tree",
"complexity": "O(n)",
"pros": "Supports multiple evaluations"
},
"Recursion": {
"rating": "⭐⭐⭐",
"approach": "Recursive descent",
"complexity": "O(n)",
"pros": "Elegant for simple grammars"
}
},
"Finding Min/Max": {
"MinStack": {
"rating": "⭐⭐⭐⭐⭐",
"approach": "Auxiliary min stack",
"complexity": "O(1) getMin",
"pros": "Best if need stack + min"
},
"Heap": {
"rating": "⭐⭐⭐⭐",
"approach": "Min/max heap",
"complexity": "O(log n) insert/delete",
"pros": "Better if not using stack"
},
"SortedList": {
"rating": "⭐⭐",
"approach": "Keep sorted",
"complexity": "O(n) insert",
"pros": "Can access all in order"
}
},
"Graph DFS": {
"Stack": {
"rating": "⭐⭐⭐⭐⭐",
"approach": "Explicit stack",
"complexity": "O(V + E)",
"pros": "Iterative, no recursion limit"
},
"Recursion": {
"rating": "⭐⭐⭐⭐",
"approach": "Recursive DFS",
"complexity": "O(V + E)",
"pros": "Simpler code"
},
"Queue": {
"rating": "⭐",
"approach": "Would give BFS not DFS",
"complexity": "N/A",
"pros": "Wrong tool"
}
}
}
return problems
8. Edge Cases and Limitations
8.1 Common Edge Cases
Empty Stack Operations:
def empty_stack_edge_cases():
"""Handle operations on empty stack"""
class SafeStack:
def __init__(self):
self.items = []
def pop_safe(self):
"""Safe pop with error handling"""
if not self.items:
raise IndexError("Cannot pop from empty stack")
return self.items.pop()
def peek_safe(self):
"""Safe peek with error handling"""
if not self.items:
raise IndexError("Cannot peek empty stack")
return self.items[-1]
def pop_with_default(self, default=None):
"""Pop with default value"""
return self.items.pop() if self.items else default
def peek_with_default(self, default=None):
"""Peek with default value"""
return self.items[-1] if self.items else default
# Edge case examples
def test_edge_cases():
stack = SafeStack()
# Edge case 1: Pop from empty
try:
stack.pop_safe()
except IndexError as e:
print(f"Caught: {e}")
# Edge case 2: Peek empty
result = stack.peek_with_default(default=0)
print(f"Peeked empty stack: {result}") # 0
# Edge case 3: Multiple pops
stack.items = [1, 2, 3]
while True:
val = stack.pop_with_default(None)
if val is None:
break
print(val)
Single Element Edge Cases:
def single_element_edge_cases():
"""Handle single element scenarios"""
# Min stack with one element
def test_min_stack_single():
min_stack = MinStack()
min_stack.push(5)
assert min_stack.top() == 5
assert min_stack.getMin() == 5
min_stack.pop()
# Now empty - should handle gracefully
# Next greater element with single element
def test_nge_single():
result = next_greater_element([5])
assert result == [-1] # No greater element
# Balanced parentheses with single bracket
def test_balanced_single():
assert is_balanced_parentheses("(") == False
assert is_balanced_parentheses(")") == False
assert is_balanced_parentheses("") == True
Stack Overflow Edge Cases:
def stack_overflow_edge_cases():
"""Handle stack overflow scenarios"""
class BoundedStack:
"""Stack with maximum capacity"""
def __init__(self, max_size):
self.max_size = max_size
self.items = []
def push(self, item):
if len(self.items) >= self.max_size:
raise OverflowError(f"Stack overflow: max size {self.max_size}")
self.items.append(item)
def is_full(self):
return len(self.items) >= self.max_size
# Recursive depth limit
def factorial_with_depth_limit(n, max_depth=1000):
"""Prevent stack overflow in recursion"""
if n > max_depth:
raise RecursionError(f"Recursion depth {n} exceeds limit {max_depth}")
if n <= 1:
return 1
return n * factorial_with_depth_limit(n - 1, max_depth)
# Iterative alternative for deep recursion
def factorial_iterative(n):
"""No stack depth limit"""
result = 1
for i in range(2, n + 1):
result *= i
return result
8.2 Expression Evaluation Edge Cases
def expression_edge_cases():
"""Edge cases in expression evaluation"""
def handle_division_by_zero():
"""Handle division by zero"""
def safe_evaluate(expression):
try:
return evaluate_postfix(expression)
except ZeroDivisionError:
return "Error: Division by zero"
# Example: "5 0 /" should handle gracefully
result = safe_evaluate("5 0 /")
print(result)
def handle_empty_expression():
"""Handle empty or whitespace-only expressions"""
def evaluate_safe(expression):
if not expression or expression.isspace():
return 0 # or raise ValueError
return evaluate_postfix(expression)
def handle_malformed_expression():
"""Handle malformed expressions"""
def validate_expression(expression):
"""Check if expression is valid before evaluation"""
tokens = expression.split()
operators = set('+-*/')
operand_count = 0
for token in tokens:
if token in operators:
if operand_count < 2:
raise ValueError("Invalid expression: insufficient operands")
operand_count -= 1
else:
operand_count += 1
if operand_count != 1:
raise ValueError("Invalid expression: wrong operand count")
return True
def handle_unmatched_parentheses():
"""Handle unmatched parentheses"""
test_cases = [
("(()", False), # Missing closing
("())", False), # Extra closing
("(()())", True), # Balanced
(")(", False), # Wrong order
("", True) # Empty (valid)
]
for expr, expected in test_cases:
result = is_balanced_parentheses(expr)
assert result == expected, f"Failed for {expr}"
8.3 Parentheses Edge Cases
def parentheses_edge_cases():
"""Comprehensive parentheses edge cases"""
edge_cases = {
# Empty cases
"": True,
" ": True, # Only whitespace
# Single brackets
"(": False,
")": False,
"[": False,
"]": False,
# Mismatched types
"(]": False,
"([)]": False,
"{[}]": False,
# Correct nesting
"()": True,
"()[]{}": True,
"{[()]}": True,
"((()))": True,
# Interleaved (invalid)
"([)]": False,
"{[(])}": False,
# With other characters
"a(b)c": True,
"a(b[c]d)e": True,
"a(b[c)d]e": False,
# Long sequences
"(" * 1000 + ")" * 1000: True,
"(" * 1000 + ")" * 999: False,
# Multiple types
"()[]{}": True,
"({[]})": True,
"()[]{}()": True
}
for expression, expected in edge_cases.items():
result = is_balanced_parentheses(expression)
assert result == expected, \
f"Failed: '{expression}' expected {expected}, got {result}"
8.4 Monotonic Stack Edge Cases
def monotonic_stack_edge_cases():
"""Edge cases for monotonic stack problems"""
# All elements equal
def test_all_equal():
arr = [5, 5, 5, 5, 5]
result = next_greater_element(arr)
assert result == [-1, -1, -1, -1, -1]
# Strictly increasing
def test_increasing():
arr = [1, 2, 3, 4, 5]
result = next_greater_element(arr)
# Each element's NGE is the next element
assert result == [2, 3, 4, 5, -1]
# Strictly decreasing
def test_decreasing():
arr = [5, 4, 3, 2, 1]
result = next_greater_element(arr)
# No greater elements to the right
assert result == [-1, -1, -1, -1, -1]
# Single element
def test_single():
arr = [42]
result = next_greater_element(arr)
assert result == [-1]
# Large numbers
def test_large_numbers():
arr = [10**9, 10**9 + 1, 10**9 - 1]
result = next_greater_element(arr)
assert result == [10**9 + 1, -1, -1]
# Negative numbers
def test_negatives():
arr = [-1, -5, -3, -2]
result = next_greater_element(arr)
assert result == [-1, -3, -2, -1]
# Mix of positive and negative
def test_mixed():
arr = [-3, 0, 2, -1, 5]
result = next_greater_element(arr)
assert result == [0, 2, 5, 5, -1]
8.5 Memory and Performance Limitations
Stack Depth Limitations:
def stack_depth_limitations():
"""Understand stack depth limits"""
import sys
# Check recursion limit
print(f"Recursion limit: {sys.getrecursionlimit()}")
# Typically ~1000 in Python
# Deep recursion fails
def deep_recursion(n):
"""Will fail for large n"""
if n == 0:
return 0
return 1 + deep_recursion(n - 1)
# Solution 1: Increase limit (not recommended)
def increase_limit_example():
sys.setrecursionlimit(10000) # Dangerous!
# May cause segmentation fault
# Solution 2: Use iteration
def iterative_solution(n):
"""No recursion depth limit"""
stack = [n]
result = 0
while stack:
val = stack.pop()
if val > 0:
result += 1
stack.append(val - 1)
return result
# Solution 3: Tail recursion optimization (manual)
def tail_recursive_optimized(n, acc=0):
"""Can be converted to iteration"""
if n == 0:
return acc
# Instead of recursion, use loop
while n > 0:
acc += 1
n -= 1
return acc
Memory Overflow:
def memory_overflow_handling():
"""Handle large stack sizes"""
class MemoryAwareStack:
"""Stack with memory limits"""
def __init__(self, max_memory_mb=100):
self.items = []
self.max_memory = max_memory_mb * 1024 * 1024 # bytes
self.current_memory = 0
def push(self, item):
import sys
item_size = sys.getsizeof(item)
if self.current_memory + item_size > self.max_memory:
raise MemoryError(f"Stack memory limit exceeded")
self.items.append(item)
self.current_memory += item_size
def pop(self):
if not self.items:
raise IndexError("Stack is empty")
item = self.items.pop()
import sys
self.current_memory -= sys.getsizeof(item)
return item
# Large object handling
def handle_large_objects():
"""Use references instead of copying"""
# Bad: Copying large objects
large_stack_bad = []
large_data = list(range(1000000))
large_stack_bad.append(large_data[:]) # Copy!
# Good: Store references
large_stack_good = []
large_stack_good.append(large_data) # Reference
8.6 Numeric Overflow in Calculations
def numeric_overflow_handling():
"""Handle numeric overflow in stack calculations"""
def safe_arithmetic_stack():
"""Check for overflow in arithmetic operations"""
import sys
def safe_add(a, b):
if a > 0 and b > sys.maxsize - a:
raise OverflowError("Addition overflow")
if a < 0 and b < -sys.maxsize - a:
raise OverflowError("Addition underflow")
return a + b
def safe_multiply(a, b):
if a > 0 and b > 0 and a > sys.maxsize // b:
raise OverflowError("Multiplication overflow")
return a * b
# Use in expression evaluation
def evaluate_with_overflow_check(expression):
stack = []
for token in expression.split():
if token == '+':
b, a = stack.pop(), stack.pop()
stack.append(safe_add(a, b))
elif token == '*':
b, a = stack.pop(), stack.pop()
stack.append(safe_multiply(a, b))
else:
stack.append(int(token))
return stack[0]
# Use arbitrary precision (Python default)
def arbitrary_precision_example():
"""Python handles arbitrary precision automatically"""
stack = []
stack.append(10**100) # Very large number
stack.append(10**100)
result = stack.pop() + stack.pop() # No overflow!
return result
8.7 Concurrent Access Edge Cases
def concurrent_access_edge_cases():
"""Handle concurrent stack access"""
import threading
from threading import Lock
class ThreadSafeStack:
"""Stack safe for concurrent access"""
def __init__(self):
self.items = []
self.lock = Lock()
def push(self, item):
with self.lock:
self.items.append(item)
def pop(self):
with self.lock:
if not self.items:
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
with self.lock:
if not self.items:
raise IndexError("Stack is empty")
return self.items[-1]
# Edge case: Race condition
def demonstrate_race_condition():
"""Show why locking is needed"""
unsafe_stack = []
def unsafe_push_pop():
for _ in range(1000):
unsafe_stack.append(1)
if unsafe_stack:
unsafe_stack.pop()
# Create multiple threads
threads = [threading.Thread(target=unsafe_push_pop) for _ in range(10)]
for t in threads:
t.start()
for t in threads:
t.join()
# Stack may not be empty due to race conditions!
print(f"Stack size after concurrent ops: {len(unsafe_stack)}")
# Edge case: Deadlock prevention
class DeadlockSafeStack:
"""Prevent deadlock with timeout"""
def __init__(self):
self.items = []
self.lock = Lock()
def push_with_timeout(self, item, timeout=1.0):
if self.lock.acquire(timeout=timeout):
try:
self.items.append(item)
finally:
self.lock.release()
else:
raise TimeoutError("Could not acquire lock")
9. Practical Mastery
9.1 Implementation Best Practices
Production-Ready Stack:
class ProductionStack:
"""
Production-quality stack implementation
Features:
- Type checking
- Capacity limits
- Thread safety (optional)
- Logging
- Error handling
"""
def __init__(self, max_size=None, thread_safe=False, element_type=None):
self.items = []
self.max_size = max_size
self.element_type = element_type
# Thread safety
if thread_safe:
from threading import Lock
self.lock = Lock()
else:
from contextlib import nullcontext
self.lock = nullcontext()
# Statistics
self.stats = {
'push_count': 0,
'pop_count': 0,
'peak_size': 0
}
def push(self, item):
"""Add item with validation"""
# Type checking
if self.element_type and not isinstance(item, self.element_type):
raise TypeError(f"Expected {self.element_type}, got {type(item)}")
with self.lock:
# Capacity check
if self.max_size and len(self.items) >= self.max_size:
raise OverflowError(f"Stack capacity {self.max_size} exceeded")
self.items.append(item)
# Update statistics
self.stats['push_count'] += 1
self.stats['peak_size'] = max(self.stats['peak_size'], len(self.items))
def pop(self):
"""Remove and return top item"""
with self.lock:
if not self.items:
raise IndexError("Cannot pop from empty stack")
item = self.items.pop()
self.stats['pop_count'] += 1
return item
def peek(self):
"""View top item without removing"""
with self.lock:
if not self.items:
raise IndexError("Cannot peek empty stack")
return self.items[-1]
def is_empty(self):
"""Check if stack is empty"""
with self.lock:
return len(self.items) == 0
def size(self):
"""Get current size"""
with self.lock:
return len(self.items)
def clear(self):
"""Remove all elements"""
with self.lock:
self.items.clear()
def __str__(self):
"""String representation"""
with self.lock:
return f"Stack({self.items}) [size={len(self.items)}]"
def __len__(self):
"""Support len() function"""
return self.size()
def __iter__(self):
"""Make iterable (bottom to top)"""
with self.lock:
return iter(self.items)
def __contains__(self, item):
"""Support 'in' operator"""
with self.lock:
return item in self.items
def get_stats(self):
"""Get usage statistics"""
with self.lock:
return self.stats.copy()
Common Mistakes and How to Avoid:
def common_stack_mistakes():
"""
Document common mistakes and solutions
"""
mistakes = [
{
"mistake": "Not checking empty before pop/peek",
"wrong": """
stack = []
top = stack[-1] # IndexError if empty!
item = stack.pop()
""",
"correct": """
stack = []
if stack:
top = stack[-1]
item = stack.pop()
else:
# Handle empty case
pass
"""
},
{
"mistake": "Modifying stack during iteration",
"wrong": """
for item in stack:
if condition:
stack.pop() # Changes size during iteration!
""",
"correct": """
# Create copy for iteration
for item in list(stack):
if condition:
stack.remove(item)
"""
},
{
"mistake": "Using stack for random access",
"wrong": """
# Accessing middle elements
middle = stack[len(stack) // 2] # Wrong data structure!
""",
"correct": """
# Use list/array for random access
data = [1, 2, 3, 4, 5]
middle = data[len(data) // 2]
"""
},
{
"mistake": "Not handling stack overflow",
"wrong": """
def factorial(n):
if n <= 1: return 1
return n * factorial(n-1) # Stack overflow for large n!
""",
"correct": """
def factorial(n):
result = 1
for i in range(2, n+1):
result *= i
return result
"""
},
{
"mistake": "Forgetting operator precedence in expressions",
"wrong": """
# "2 + 3 * 4" should be 14, not 20
result = (2 + 3) * 4 # Wrong!
""",
"correct": """
# Use proper precedence handling
result = 2 + (3 * 4) # Correct
# Or use stack-based parser with precedence
"""
}
]
return mistakes
9.2 Testing Strategies
import unittest
class TestStack(unittest.TestCase):
"""Comprehensive stack test suite"""
def setUp(self):
"""Set up test fixtures"""
self.stack = ProductionStack()
def tearDown(self):
"""Clean up after tests"""
self.stack.clear()
# Test basic operations
def test_push_and_pop(self):
"""Test push and pop operations"""
self.stack.push(1)
self.stack.push(2)
self.stack.push(3)
self.assertEqual(self.stack.pop(), 3)
self.assertEqual(self.stack.pop(), 2)
self.assertEqual(self.stack.pop(), 1)
def test_peek(self):
"""Test peek operation"""
self.stack.push(42)
self.assertEqual(self.stack.peek(), 42)
self.assertEqual(self.stack.size(), 1) # Size unchanged
def test_is_empty(self):
"""Test empty check"""
self.assertTrue(self.stack.is_empty())
self.stack.push(1)
self.assertFalse(self.stack.is_empty())
# Test edge cases
def test_pop_empty_stack(self):
"""Test popping from empty stack"""
with self.assertRaises(IndexError):
self.stack.pop()
def test_peek_empty_stack(self):
"""Test peeking empty stack"""
with self.assertRaises(IndexError):
self.stack.peek()
def test_capacity_limit(self):
"""Test stack capacity limit"""
limited_stack = ProductionStack(max_size=3)
limited_stack.push(1)
limited_stack.push(2)
limited_stack.push(3)
with self.assertRaises(OverflowError):
limited_stack.push(4)
# Test type safety
def test_type_checking(self):
"""Test type enforcement"""
typed_stack = ProductionStack(element_type=int)
typed_stack.push(1)
typed_stack.push(2)
with self.assertRaises(TypeError):
typed_stack.push("string")
# Test LIFO property
def test_lifo_order(self):
"""Test LIFO ordering"""
items = [1, 2, 3, 4, 5]
for item in items:
self.stack.push(item)
popped = []
while not self.stack.is_empty():
popped.append(self.stack.pop())
self.assertEqual(popped, items[::-1])
# Test with large data
def test_large_stack(self):
"""Test with many elements"""
n = 10000
for i in range(n):
self.stack.push(i)
self.assertEqual(self.stack.size(), n)
for i in range(n-1, -1, -1):
self.assertEqual(self.stack.pop(), i)
# Test statistics
def test_statistics(self):
"""Test usage statistics"""
self.stack.push(1)
self.stack.push(2)
self.stack.push(3)
self.stack.pop()
stats = self.stack.get_stats()
self.assertEqual(stats['push_count'], 3)
self.assertEqual(stats['pop_count'], 1)
self.assertEqual(stats['peak_size'], 3)
# Algorithm-specific tests
class TestStackAlgorithms(unittest.TestCase):
"""Test stack-based algorithms"""
def test_balanced_parentheses(self):
"""Test parentheses validation"""
test_cases = [
("()", True),
("()[]{}", True),
("(]", False),
("([)]", False),
("{[]}", True)
]
for expr, expected in test_cases:
self.assertEqual(is_balanced_parentheses(expr), expected)
def test_next_greater_element(self):
"""Test NGE algorithm"""
test_cases = [
([4, 5, 2, 10], [5, 10, 10, -1]),
([13, 7, 6, 12], [12, -1, 12, -1]),
([1, 2, 3, 4], [2, 3, 4, -1])
]
for arr, expected in test_cases:
self.assertEqual(next_greater_element(arr), expected)
def test_postfix_evaluation(self):
"""Test expression evaluation"""
test_cases = [
("2 3 +", 5),
("2 3 + 4 *", 20),
("5 1 2 + 4 * + 3 -", 14)
]
for expr, expected in test_cases:
self.assertEqual(evaluate_postfix(expr), expected)
9.3 Debugging Techniques
class DebuggableStack:
"""Stack with debugging capabilities"""
def __init__(self, debug=False):
self.items = []
self.debug = debug
self.operation_log = []
def push(self, item):
"""Push with logging"""
self.items.append(item)
if self.debug:
self.operation_log.append(f"PUSH {item} → {self.items}")
print(f"[DEBUG] After push({item}): {self.items}")
def pop(self):
"""Pop with logging"""
if not self.items:
if self.debug:
print("[DEBUG] Attempted pop on empty stack!")
raise IndexError("Stack is empty")
item = self.items.pop()
if self.debug:
self.operation_log.append(f"POP {item} → {self.items}")
print(f"[DEBUG] After pop(): {item}, remaining: {self.items}")
return item
def visualize(self):
"""Visual representation of stack"""
if not self.items:
print("Empty Stack")
return
print("\n┌─────┐")
for i in range(len(self.items) - 1, -1, -1):
item = self.items[i]
marker = " ← TOP" if i == len(self.items) - 1 else ""
print(f"│ {item:3} │{marker}")
print("└─────┘")
def get_operation_log(self):
"""Get history of operations"""
return self.operation_log
# Step-by-step debugging
def debug_expression_evaluation(expression):
"""Debug expression evaluation step by step"""
print(f"Evaluating: {expression}")
print("="*50)
stack = DebuggableStack(debug=True)
tokens = expression.split()
for i, token in enumerate(tokens):
print(f"\nStep {i+1}: Processing '{token}'")
if token.isdigit():
stack.push(int(token))
elif token in '+-*/':
b = stack.pop()
a = stack.pop()
if token == '+': result = a + b
elif token == '-': result = a - b
elif token == '*': result = a * b
elif token == '/': result = a / b
print(f" Compute: {a} {token} {b} = {result}")
stack.push(result)
print(f"\nFinal result: {stack.pop()}")
print("="*50)
9.4 Common Interview Patterns
def interview_stack_patterns():
"""
Common patterns in stack interview questions
"""
patterns = {
"Pattern 1: Monotonic Stack": {
"description": "Maintain stack in monotonic order",
"use_cases": [
"Next Greater Element",
"Stock Span",
"Largest Rectangle",
"Daily Temperatures"
],
"template": """
stack = []
result = []
for i, val in enumerate(arr):
# Pop elements not satisfying monotonic property
while stack and arr[stack[-1]] < val: # or >
result[stack.pop()] = val
stack.append(i)
"""
},
"Pattern 2: Expression Parsing": {
"description": "Use stack to handle operator precedence",
"use_cases": [
"Basic Calculator",
"Evaluate RPN",
"Infix to Postfix"
],
"template": """
operands = []
operators = []
for token in expression:
if is_operand(token):
operands.push(token)
elif is_operator(token):
while should_pop_operator(operators, token):
evaluate_top(operands, operators)
operators.push(token)
"""
},
"Pattern 3: Matching/Validation": {
"description": "Match opening with closing elements",
"use_cases": [
"Balanced Parentheses",
"Valid Parentheses",
"Remove Invalid Parentheses"
],
"template": """
stack = []
for char in string:
if is_opening(char):
stack.push(char)
elif is_closing(char):
if not stack or not matches(stack.top(), char):
return False
stack.pop()
return stack.is_empty()
"""
},
"Pattern 4: DFS/Backtracking": {
"description": "Use stack for depth-first exploration",
"use_cases": [
"Clone Graph",
"Number of Islands",
"Path in Graph"
],
"template": """
stack = [start_node]
visited = set()
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
process(node)
for neighbor in get_neighbors(node):
stack.push(neighbor)
"""
},
"Pattern 5: Two Stack Design": {
"description": "Use two stacks for special functionality",
"use_cases": [
"Min Stack",
"Queue using Stacks",
"Stack with getMin"
],
"template": """
main_stack = []
auxiliary_stack = []
def push(val):
main_stack.push(val)
# Update auxiliary based on problem
aux_val = compute_aux(val, auxiliary_stack.top())
auxiliary_stack.push(aux_val)
"""
}
}
return patterns
def quick_reference_guide():
"""Quick reference for stack problems"""
guide = {
"When to use Stack": [
"Need LIFO ordering",
"Processing nested structures",
"Reversing data",
"Matching pairs (parentheses)",
"DFS traversal",
"Expression evaluation",
"Backtracking"
],
"Quick Checks": [
"Can I solve with just top element?",
"Do I need to match/pair elements?",
"Is there a nesting structure?",
"Do I need to backtrack?",
"Am I processing in reverse order?"
],
"Common Operations": {
"push(x)": "Add to top",
"pop()": "Remove from top",
"peek()": "View top without removing",
"isEmpty()": "Check if empty"
},
"Time Complexities": {
"Basic ops": "O(1)",
"Search": "O(n)",
"Monotonic stack": "O(n) amortized",
"Expression eval": "O(n)"
}
}
return guide
9.5 Real-World Applications
def real_world_stack_applications():
"""
Real-world applications of stacks
"""
applications = {
"Browser History": {
"description": "Back/forward navigation",
"implementation": """
class BrowserHistory:
def __init__(self):
self.back_stack = []
self.forward_stack = []
self.current = None
def visit(self, url):
if self.current:
self.back_stack.append(self.current)
self.current = url
self.forward_stack.clear() # Clear forward history
def back(self):
if self.back_stack:
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
def forward(self):
if self.forward_stack:
self.back_stack.append(self.current)
self.current = self.forward_stack.pop()
return self.current
"""
},
"Text Editor Undo/Redo": {
"description": "Undo and redo operations",
"implementation": """
class TextEditor:
def __init__(self):
self.text = ""
self.undo_stack = []
self.redo_stack = []
def write(self, text):
self.undo_stack.append(('write', self.text))
self.text += text
self.redo_stack.clear()
def undo(self):
if self.undo_stack:
operation, prev_text = self.undo_stack.pop()
self.redo_stack.append(('undo', self.text))
self.text = prev_text
def redo(self):
if self.redo_stack:
operation, next_text = self.redo_stack.pop()
self.undo_stack.append(('redo', self.text))
self.text = next_text
"""
},
"Function Call Stack": {
"description": "Manage function calls and local variables",
"explanation": """
When a function is called:
1. Current state is pushed to call stack
2. New stack frame created with:
- Return address
- Parameters
- Local variables
3. When function returns, frame is popped
4. Execution resumes at return address
"""
},
"Expression Calculators": {
"description": "Scientific calculators, RPN calculators",
"implementation": """
class RPNCalculator:
def __init__(self):
self.stack = []
def enter(self, number):
self.stack.append(number)
def add(self):
b, a = self.stack.pop(), self.stack.pop()
self.stack.append(a + b)
def multiply(self):
b, a = self.stack.pop(), self.stack.pop()
self.stack.append(a * b)
def result(self):
return self.stack[-1] if self.stack else 0
"""
},
"Syntax Checking": {
"description": "Compilers and IDEs check syntax",
"use_case": """
- Matching brackets in code
- Checking HTML/XML tag nesting
- Validating JSON structure
- Parsing programming languages
"""
}
}
return applications
9.6 Complete Implementations - Topic 38: Stack Data Structure
Topic 38: Array-Based and Linked List Stack Variants
class DynamicArrayStack:
"""
Dynamic array-based stack with automatic resizing
Features:
- Automatic capacity doubling when full
- Automatic shrinking when 1/4 full
- Amortized O(1) push and pop
- Memory efficient
"""
def __init__(self, initial_capacity=8):
"""Initialize with small capacity"""
self.capacity = initial_capacity
self.data = [None] * self.capacity
self.size = 0
def push(self, item):
"""
O(1) amortized - Add item with automatic resizing
Doubles capacity when full to maintain amortized O(1)
"""
if self.size == self.capacity:
self._resize(2 * self.capacity)
self.data[self.size] = item
self.size += 1
def pop(self):
"""
O(1) amortized - Remove with automatic shrinking
Shrinks to half when only 1/4 full to save memory
while avoiding thrashing
"""
if self.size == 0:
raise IndexError("pop from empty stack")
self.size -= 1
item = self.data[self.size]
self.data[self.size] = None # Prevent memory leak
# Shrink if only 1/4 full (avoid thrashing)
if self.size > 0 and self.size == self.capacity // 4:
self._resize(self.capacity // 2)
return item
def peek(self):
"""O(1) - View top without removing"""
if self.size == 0:
raise IndexError("peek from empty stack")
return self.data[self.size - 1]
def is_empty(self):
"""O(1) - Check if empty"""
return self.size == 0
def __len__(self):
"""O(1) - Get size"""
return self.size
def _resize(self, new_capacity):
"""
O(n) - Resize internal array
Called infrequently, so amortized cost is O(1)
"""
new_data = [None] * new_capacity
for i in range(self.size):
new_data[i] = self.data[i]
self.data = new_data
self.capacity = new_capacity
def get_capacity(self):
"""Return current capacity"""
return self.capacity
def __str__(self):
"""String representation"""
items = [self.data[i] for i in range(self.size)]
return f"DynamicStack({items}) [size={self.size}, cap={self.capacity}]"
class CircularArrayStack:
"""
Circular array-based stack for memory efficiency
Reuses array space without shifting elements
Useful when stack grows and shrinks frequently
"""
def __init__(self, capacity=100):
"""Initialize circular buffer"""
self.capacity = capacity
self.data = [None] * capacity
self.top = -1 # Points to top element
self.count = 0
def push(self, item):
"""O(1) - Add to circular buffer"""
if self.count == self.capacity:
raise OverflowError("Stack is full")
self.top = (self.top + 1) % self.capacity
self.data[self.top] = item
self.count += 1
def pop(self):
"""O(1) - Remove from circular buffer"""
if self.count == 0:
raise IndexError("Stack is empty")
item = self.data[self.top]
self.data[self.top] = None
self.top = (self.top - 1) % self.capacity
self.count -= 1
return item
def peek(self):
"""O(1) - View top"""
if self.count == 0:
raise IndexError("Stack is empty")
return self.data[self.top]
def is_empty(self):
"""O(1) - Check if empty"""
return self.count == 0
def size(self):
"""O(1) - Get size"""
return self.count
class DoublyLinkedStack:
"""
Doubly linked list stack for advanced operations
Supports:
- Standard stack operations
- Access to bottom element
- Reverse iteration
- O(1) concatenation
"""
class Node:
"""Node with prev and next pointers"""
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
def __init__(self):
"""Initialize empty stack with sentinels"""
# Use sentinel nodes to simplify edge cases
self.head = self.Node(None) # Bottom sentinel
self.tail = self.Node(None) # Top sentinel
self.head.next = self.tail
self.tail.prev = self.head
self.count = 0
def push(self, data):
"""
O(1) - Add to top
Insert before tail sentinel
"""
new_node = self.Node(data)
new_node.prev = self.tail.prev
new_node.next = self.tail
self.tail.prev.next = new_node
self.tail.prev = new_node
self.count += 1
def pop(self):
"""
O(1) - Remove from top
Remove node before tail sentinel
"""
if self.is_empty():
raise IndexError("Stack is empty")
node = self.tail.prev
node.prev.next = self.tail
self.tail.prev = node.prev
self.count -= 1
return node.data
def peek(self):
"""O(1) - View top"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.tail.prev.data
def bottom(self):
"""O(1) - View bottom element"""
if self.is_empty():
raise IndexError("Stack is empty")
return self.head.next.data
def is_empty(self):
"""O(1) - Check if empty"""
return self.count == 0
def size(self):
"""O(1) - Get size"""
return self.count
def reverse_iterator(self):
"""
O(n) - Iterate from bottom to top
Useful for printing or processing in reverse
"""
current = self.head.next
while current != self.tail:
yield current.data
current = current.next
def concatenate(self, other_stack):
"""
O(1) - Concatenate another stack on top
Other stack becomes empty after concatenation
"""
if other_stack.is_empty():
return
# Connect this stack's top to other's bottom
self.tail.prev.next = other_stack.head.next
other_stack.head.next.prev = self.tail.prev
# Update tail
self.tail = other_stack.tail
self.count += other_stack.count
# Clear other stack
other_stack.head.next = other_stack.tail
other_stack.tail.prev = other_stack.head
other_stack.count = 0
class MultiStack:
"""
Multiple stacks in single array
Efficiently implements k stacks in one array
Good for memory locality and cache performance
"""
def __init__(self, num_stacks, stack_capacity):
"""
Initialize k stacks
Args:
num_stacks: Number of stacks
stack_capacity: Capacity per stack
"""
self.num_stacks = num_stacks
self.stack_capacity = stack_capacity
self.array_size = num_stacks * stack_capacity
self.data = [None] * self.array_size
# Track top of each stack
self.tops = [-1] * num_stacks
def push(self, stack_num, value):
"""
O(1) - Push to specific stack
Args:
stack_num: Stack index (0 to k-1)
value: Value to push
"""
if stack_num < 0 or stack_num >= self.num_stacks:
raise ValueError(f"Invalid stack number: {stack_num}")
if self.tops[stack_num] + 1 >= self.stack_capacity:
raise OverflowError(f"Stack {stack_num} is full")
self.tops[stack_num] += 1
index = stack_num * self.stack_capacity + self.tops[stack_num]
self.data[index] = value
def pop(self, stack_num):
"""
O(1) - Pop from specific stack
Args:
stack_num: Stack index (0 to k-1)
Returns:
Popped value
"""
if stack_num < 0 or stack_num >= self.num_stacks:
raise ValueError(f"Invalid stack number: {stack_num}")
if self.tops[stack_num] < 0:
raise IndexError(f"Stack {stack_num} is empty")
index = stack_num * self.stack_capacity + self.tops[stack_num]
value = self.data[index]
self.data[index] = None
self.tops[stack_num] -= 1
return value
def peek(self, stack_num):
"""O(1) - Peek specific stack"""
if stack_num < 0 or stack_num >= self.num_stacks:
raise ValueError(f"Invalid stack number: {stack_num}")
if self.tops[stack_num] < 0:
raise IndexError(f"Stack {stack_num} is empty")
index = stack_num * self.stack_capacity + self.tops[stack_num]
return self.data[index]
def is_empty(self, stack_num):
"""O(1) - Check if specific stack is empty"""
if stack_num < 0 or stack_num >= self.num_stacks:
raise ValueError(f"Invalid stack number: {stack_num}")
return self.tops[stack_num] < 0
def size(self, stack_num):
"""O(1) - Get size of specific stack"""
if stack_num < 0 or stack_num >= self.num_stacks:
raise ValueError(f"Invalid stack number: {stack_num}")
return self.tops[stack_num] + 1
# Comprehensive test cases for Topic 38
def test_stack_implementations():
"""Test all stack variants"""
print("Testing DynamicArrayStack:")
dyn_stack = DynamicArrayStack(initial_capacity=2)
print(f"Initial capacity: {dyn_stack.get_capacity()}")
# Test resizing
for i in range(10):
dyn_stack.push(i)
print(f"After push({i}): size={len(dyn_stack)}, cap={dyn_stack.get_capacity()}")
# Test shrinking
for i in range(7):
val = dyn_stack.pop()
print(f"After pop(): {val}, size={len(dyn_stack)}, cap={dyn_stack.get_capacity()}")
print("\nTesting CircularArrayStack:")
circ_stack = CircularArrayStack(capacity=5)
for i in range(5):
circ_stack.push(i)
print(f"Stack size: {circ_stack.size()}")
print("\nTesting DoublyLinkedStack:")
dll_stack = DoublyLinkedStack()
for i in range(5):
dll_stack.push(i)
print(f"Top: {dll_stack.peek()}, Bottom: {dll_stack.bottom()}")
print("Bottom to top:", list(dll_stack.reverse_iterator()))
# Test concatenation
stack2 = DoublyLinkedStack()
for i in range(5, 8):
stack2.push(i)
dll_stack.concatenate(stack2)
print("After concat:", list(dll_stack.reverse_iterator()))
print("\nTesting MultiStack:")
multi = MultiStack(num_stacks=3, stack_capacity=5)
multi.push(0, 10)
multi.push(0, 20)
multi.push(1, 30)
multi.push(2, 40)
print(f"Stack 0 top: {multi.peek(0)}")
print(f"Stack 1 top: {multi.peek(1)}")
print(f"Stack 2 top: {multi.peek(2)}")
9.7 Complete Implementations - Topic 39: Stack Operations
Topic 39: Advanced Stack Operations
class AdvancedStack:
"""
Stack with advanced operations beyond push/pop
Supports:
- Multi-push/pop
- Search
- Reverse
- Sort
- Filter
- Map
- Reduce
"""
def __init__(self):
"""Initialize empty stack"""
self.items = []
# Basic operations
def push(self, item):
"""O(1) - Push single item"""
self.items.append(item)
def pop(self):
"""O(1) - Pop single item"""
if not self.items:
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
"""O(1) - View top"""
if not self.items:
raise IndexError("Stack is empty")
return self.items[-1]
# Advanced operations
def multi_push(self, *items):
"""
O(k) - Push multiple items at once
Args:
*items: Variable number of items to push
Example:
stack.multi_push(1, 2, 3, 4)
"""
self.items.extend(items)
def multi_pop(self, count):
"""
O(k) - Pop multiple items at once
Args:
count: Number of items to pop
Returns:
List of popped items (top to bottom)
Example:
items = stack.multi_pop(3) # [top, second, third]
"""
if count > len(self.items):
raise IndexError(f"Cannot pop {count} items from stack of size {len(self.items)}")
result = []
for _ in range(count):
result.append(self.pop())
return result
def search(self, item):
"""
O(n) - Find item in stack
Args:
item: Item to search for
Returns:
Distance from top (1-indexed), or -1 if not found
Example:
Stack: [1, 2, 3, 4, 5] (5 is top)
search(5) = 1 # Top element
search(3) = 3 # Third from top
search(99) = -1 # Not found
"""
try:
# Find from top
for i in range(len(self.items) - 1, -1, -1):
if self.items[i] == item:
return len(self.items) - i
return -1
except:
return -1
def reverse(self):
"""
O(n) - Reverse stack in place
Uses recursion to reverse without extra space
"""
if not self.is_empty():
item = self.pop()
self.reverse()
self._insert_at_bottom(item)
def _insert_at_bottom(self, item):
"""
O(n) - Helper to insert item at bottom
Used by reverse operation
"""
if self.is_empty():
self.push(item)
else:
temp = self.pop()
self._insert_at_bottom(item)
self.push(temp)
def sort(self, reverse=False):
"""
O(n²) - Sort stack using another stack
Args:
reverse: If True, sort descending; else ascending
Algorithm:
1. Pop all elements to temp stack
2. For each element, find correct position
3. Insert in sorted order
"""
temp_stack = []
while not self.is_empty():
current = self.pop()
# Find position for current element
if reverse:
while temp_stack and temp_stack[-1] < current:
self.push(temp_stack.pop())
else:
while temp_stack and temp_stack[-1] > current:
self.push(temp_stack.pop())
temp_stack.append(current)
# Move sorted elements back
while temp_stack:
self.push(temp_stack.pop())
def filter(self, predicate):
"""
O(n) - Filter stack elements
Args:
predicate: Function that returns True for items to keep
Returns:
New stack with filtered elements
Example:
even_stack = stack.filter(lambda x: x % 2 == 0)
"""
result = AdvancedStack()
temp = []
# Pop all to temp
while not self.is_empty():
temp.append(self.pop())
# Push back, filtering
while temp:
item = temp.pop()
self.push(item)
if predicate(item):
result.push(item)
return result
def map(self, transform):
"""
O(n) - Transform all elements
Args:
transform: Function to apply to each element
Returns:
New stack with transformed elements
Example:
doubled = stack.map(lambda x: x * 2)
"""
result = AdvancedStack()
temp = []
# Pop all to temp
while not self.is_empty():
temp.append(self.pop())
# Push back, transforming
while temp:
item = temp.pop()
self.push(item)
result.push(transform(item))
return result
def reduce(self, operation, initial=None):
"""
O(n) - Reduce stack to single value
Args:
operation: Binary function to apply
initial: Initial value (optional)
Returns:
Single accumulated value
Example:
sum = stack.reduce(lambda a, b: a + b, 0)
product = stack.reduce(lambda a, b: a * b, 1)
"""
temp = []
# Pop all to temp
while not self.is_empty():
temp.append(self.pop())
# Process in reverse order (bottom to top)
temp.reverse()
# Restore original stack
for item in reversed(temp):
self.push(item)
# Perform reduction
if not temp:
return initial
if initial is None:
result = temp[0]
start_idx = 1
else:
result = initial
start_idx = 0
for i in range(start_idx, len(temp)):
result = operation(result, temp[i])
return result
def duplicate_top(self):
"""
O(1) - Duplicate top element
Example:
Stack: [1, 2, 3]
After duplicate_top: [1, 2, 3, 3]
"""
if not self.is_empty():
top = self.peek()
self.push(top)
def swap_top_two(self):
"""
O(1) - Swap top two elements
Example:
Stack: [1, 2, 3, 4]
After swap: [1, 2, 4, 3]
"""
if len(self.items) < 2:
raise IndexError("Need at least 2 elements to swap")
a = self.pop()
b = self.pop()
self.push(a)
self.push(b)
def rotate(self, positions=1):
"""
O(n) - Rotate stack elements
Args:
positions: Number of positions to rotate
Positive: rotate right (top to bottom)
Negative: rotate left (bottom to top)
Example:
Stack: [1, 2, 3, 4, 5] (5 is top)
rotate(1): [5, 1, 2, 3, 4] (4 is top)
rotate(-1): [2, 3, 4, 5, 1] (1 is top)
"""
if self.is_empty():
return
n = len(self.items)
positions = positions % n
# Split and recombine
temp = self.items[-positions:]
self.items = temp + self.items[:-positions]
def clear(self):
"""O(1) - Remove all elements"""
self.items.clear()
def is_empty(self):
"""O(1) - Check if empty"""
return len(self.items) == 0
def size(self):
"""O(1) - Get size"""
return len(self.items)
def to_list(self):
"""O(n) - Convert to list (bottom to top)"""
return self.items.copy()
def __str__(self):
"""String representation"""
return f"AdvancedStack({self.items})"
def __repr__(self):
"""Detailed representation"""
return f"AdvancedStack(size={len(self.items)}, items={self.items})"
# Comprehensive test cases for Topic 39
def test_advanced_operations():
"""Test all advanced stack operations"""
print("Testing multi_push and multi_pop:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3, 4, 5)
print(f"After multi_push: {stack}")
popped = stack.multi_pop(3)
print(f"Popped items: {popped}")
print(f"Remaining: {stack}")
print("\nTesting search:")
stack = AdvancedStack()
stack.multi_push(10, 20, 30, 40, 50)
print(f"Stack: {stack}")
print(f"Search 50 (top): {stack.search(50)}")
print(f"Search 30: {stack.search(30)}")
print(f"Search 99: {stack.search(99)}")
print("\nTesting reverse:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3, 4, 5)
print(f"Before reverse: {stack}")
stack.reverse()
print(f"After reverse: {stack}")
print("\nTesting sort:")
stack = AdvancedStack()
stack.multi_push(3, 1, 4, 1, 5, 9, 2, 6)
print(f"Before sort: {stack}")
stack.sort()
print(f"After sort (asc): {stack}")
stack.sort(reverse=True)
print(f"After sort (desc): {stack}")
print("\nTesting filter:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
even_stack = stack.filter(lambda x: x % 2 == 0)
print(f"Original: {stack}")
print(f"Even numbers: {even_stack}")
print("\nTesting map:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3, 4, 5)
squared = stack.map(lambda x: x ** 2)
print(f"Original: {stack}")
print(f"Squared: {squared}")
print("\nTesting reduce:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3, 4, 5)
total = stack.reduce(lambda a, b: a + b, 0)
product = stack.reduce(lambda a, b: a * b, 1)
print(f"Stack: {stack}")
print(f"Sum: {total}")
print(f"Product: {product}")
print("\nTesting duplicate and swap:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3)
print(f"Original: {stack}")
stack.duplicate_top()
print(f"After duplicate: {stack}")
stack.swap_top_two()
print(f"After swap: {stack}")
print("\nTesting rotate:")
stack = AdvancedStack()
stack.multi_push(1, 2, 3, 4, 5)
print(f"Original: {stack}")
stack.rotate(1)
print(f"Rotate right 1: {stack}")
stack.rotate(-2)
print(f"Rotate left 2: {stack}")
9.8 Complete Implementations - Topic 40: Expression Evaluation
Topic 40: Complete Expression Evaluators
class ExpressionEvaluator:
"""
Complete expression evaluation system
Supports:
- Infix to Postfix conversion
- Infix to Prefix conversion
- Postfix evaluation
- Prefix evaluation
- Direct infix evaluation
- Multiple operators and precedence levels
"""
def __init__(self):
"""Initialize with operator definitions"""
# Define precedence (higher = evaluated first)
self.precedence = {
'+': 1, '-': 1,
'*': 2, '/': 2, '%': 2,
'^': 3,
'(': 0, ')': 0
}
# Define associativity
self.right_associative = {'^'}
def is_operator(self, char):
"""Check if character is an operator"""
return char in '+-*/%^'
def is_operand(self, char):
"""Check if character is an operand"""
return char.isalnum()
def get_precedence(self, op):
"""Get operator precedence"""
return self.precedence.get(op, 0)
def is_right_associative(self, op):
"""Check if operator is right-associative"""
return op in self.right_associative
def should_pop_operator(self, stack_op, current_op):
"""
Determine if stack operator should be popped
Based on precedence and associativity
"""
if not stack_op or stack_op == '(':
return False
stack_prec = self.get_precedence(stack_op)
current_prec = self.get_precedence(current_op)
if self.is_right_associative(current_op):
return stack_prec > current_prec
else:
return stack_prec >= current_prec
def infix_to_postfix(self, expression):
"""
Convert infix to postfix notation
Args:
expression: Infix expression (e.g., "A+B*C")
Returns:
Postfix expression (e.g., "ABC*+")
Algorithm (Shunting-yard):
1. Read expression left to right
2. If operand: add to output
3. If '(': push to stack
4. If ')': pop until '(' found
5. If operator: pop higher precedence ops, then push
6. At end: pop remaining operators
Time: O(n), Space: O(n)
Examples:
"A+B*C" -> "ABC*+"
"(A+B)*C" -> "AB+C*"
"A^B^C" -> "ABC^^" (right associative)
"""
output = []
stack = []
# Tokenize expression
tokens = self._tokenize(expression)
for token in tokens:
if self.is_operand(token):
# Operand: add to output
output.append(token)
elif token == '(':
# Left paren: push to stack
stack.append(token)
elif token == ')':
# Right paren: pop until matching '('
while stack and stack[-1] != '(':
output.append(stack.pop())
if stack and stack[-1] == '(':
stack.pop() # Remove '('
else:
raise ValueError("Mismatched parentheses")
elif self.is_operator(token):
# Operator: pop higher precedence, then push
while stack and self.should_pop_operator(stack[-1], token):
output.append(stack.pop())
stack.append(token)
# Pop remaining operators
while stack:
op = stack.pop()
if op == '(' or op == ')':
raise ValueError("Mismatched parentheses")
output.append(op)
return ''.join(output)
def infix_to_prefix(self, expression):
"""
Convert infix to prefix notation
Args:
expression: Infix expression (e.g., "A+B*C")
Returns:
Prefix expression (e.g., "+A*BC")
Algorithm:
1. Reverse expression
2. Replace '(' with ')' and vice versa
3. Get postfix of modified expression
4. Reverse result
Time: O(n), Space: O(n)
Examples:
"A+B*C" -> "+A*BC"
"(A+B)*C" -> "*+ABC"
"""
# Reverse expression
tokens = self._tokenize(expression)
tokens.reverse()
# Swap parentheses
for i in range(len(tokens)):
if tokens[i] == '(':
tokens[i] = ')'
elif tokens[i] == ')':
tokens[i] = '('
# Get postfix of modified expression
reversed_expr = ''.join(tokens)
postfix = self.infix_to_postfix(reversed_expr)
# Reverse result
return postfix[::-1]
def evaluate_postfix(self, expression):
"""
Evaluate postfix expression
Args:
expression: Postfix expression (e.g., "23+4*")
Returns:
Result of evaluation
Algorithm:
1. Scan expression left to right
2. If operand: push to stack
3. If operator: pop two operands, apply operator, push result
4. Final stack contains result
Time: O(n), Space: O(n)
Examples:
"23+" -> 5
"234*+" -> 14
"52/3+" -> 5.5
"""
stack = []
# Tokenize and process
tokens = self._tokenize_with_numbers(expression)
for token in tokens:
if token.replace('.', '').replace('-', '').isdigit():
# Operand: push to stack
stack.append(float(token))
elif self.is_operator(token):
# Operator: pop two operands
if len(stack) < 2:
raise ValueError(f"Invalid expression: insufficient operands for {token}")
b = stack.pop()
a = stack.pop()
# Apply operator
result = self._apply_operator(a, b, token)
stack.append(result)
if len(stack) != 1:
raise ValueError("Invalid expression: too many operands")
return stack[0]
def evaluate_prefix(self, expression):
"""
Evaluate prefix expression
Args:
expression: Prefix expression (e.g., "+*234")
Returns:
Result of evaluation
Algorithm:
1. Scan expression right to left
2. If operand: push to stack
3. If operator: pop two operands, apply operator, push result
4. Final stack contains result
Time: O(n), Space: O(n)
Examples:
"+23" -> 5
"+*234" -> 14
"+/523" -> 5.5
"""
stack = []
# Tokenize and reverse
tokens = self._tokenize_with_numbers(expression)
tokens.reverse()
for token in tokens:
if token.replace('.', '').replace('-', '').isdigit():
# Operand: push to stack
stack.append(float(token))
elif self.is_operator(token):
# Operator: pop two operands (order matters!)
if len(stack) < 2:
raise ValueError(f"Invalid expression: insufficient operands for {token}")
a = stack.pop()
b = stack.pop()
# Apply operator
result = self._apply_operator(a, b, token)
stack.append(result)
if len(stack) != 1:
raise ValueError("Invalid expression: too many operands")
return stack[0]
def evaluate_infix(self, expression):
"""
Evaluate infix expression directly
Args:
expression: Infix expression (e.g., "2+3*4")
Returns:
Result of evaluation
Algorithm:
Uses two stacks (operands and operators)
Maintains operator precedence during evaluation
Time: O(n), Space: O(n)
Examples:
"2+3*4" -> 14
"(2+3)*4" -> 20
"2^3^2" -> 512 (right associative)
"""
operands = []
operators = []
tokens = self._tokenize_with_numbers(expression)
for token in tokens:
if token.replace('.', '').replace('-', '').isdigit():
# Operand: push to operand stack
operands.append(float(token))
elif token == '(':
# Left paren: push to operator stack
operators.append(token)
elif token == ')':
# Right paren: evaluate until '('
while operators and operators[-1] != '(':
self._evaluate_top(operands, operators)
if operators and operators[-1] == '(':
operators.pop()
else:
raise ValueError("Mismatched parentheses")
elif self.is_operator(token):
# Operator: evaluate higher precedence first
while (operators and
operators[-1] != '(' and
self.should_pop_operator(operators[-1], token)):
self._evaluate_top(operands, operators)
operators.append(token)
# Evaluate remaining operators
while operators:
self._evaluate_top(operands, operators)
if len(operands) != 1:
raise ValueError("Invalid expression")
return operands[0]
def _tokenize(self, expression):
"""
Tokenize expression (single character tokens)
Returns list of tokens
"""
return [c for c in expression if c.strip()]
def _tokenize_with_numbers(self, expression):
"""
Tokenize expression with multi-digit numbers
Returns list of tokens
"""
tokens = []
current_number = ''
for char in expression:
if char.isdigit() or char == '.':
current_number += char
elif char.isspace():
if current_number:
tokens.append(current_number)
current_number = ''
else:
if current_number:
tokens.append(current_number)
current_number = ''
if char.strip():
tokens.append(char)
if current_number:
tokens.append(current_number)
return tokens
def _apply_operator(self, a, b, op):
"""
Apply binary operator to operands
Args:
a, b: Operands
op: Operator
Returns:
Result of operation
"""
if op == '+':
return a + b
elif op == '-':
return a - b
elif op == '*':
return a * b
elif op == '/':
if b == 0:
raise ZeroDivisionError("Division by zero")
return a / b
elif op == '%':
if b == 0:
raise ZeroDivisionError("Modulo by zero")
return a % b
elif op == '^':
return a ** b
else:
raise ValueError(f"Unknown operator: {op}")
def _evaluate_top(self, operands, operators):
"""
Evaluate top operator with top two operands
Used in infix evaluation
"""
if len(operands) < 2:
raise ValueError("Insufficient operands")
b = operands.pop()
a = operands.pop()
op = operators.pop()
result = self._apply_operator(a, b, op)
operands.append(result)
# Comprehensive test cases for Topic 40
def test_expression_evaluation():
"""Test all expression evaluation methods"""
evaluator = ExpressionEvaluator()
print("Testing Infix to Postfix:")
test_cases = [
("A+B*C", "ABC*+"),
("(A+B)*C", "AB+C*"),
("A+B*C+D", "ABC*+D+"),
("(A+B)*(C+D)", "AB+CD+*"),
("A^B^C", "ABC^^"), # Right associative
]
for infix, expected in test_cases:
result = evaluator.infix_to_postfix(infix)
status = "✓" if result == expected else "✗"
print(f" {status} {infix:20} -> {result:20} (expected: {expected})")
print("\nTesting Infix to Prefix:")
test_cases = [
("A+B*C", "+A*BC"),
("(A+B)*C", "*+ABC"),
("A+B*C+D", "++A*BCD"),
]
for infix, expected in test_cases:
result = evaluator.infix_to_prefix(infix)
status = "✓" if result == expected else "✗"
print(f" {status} {infix:20} -> {result:20} (expected: {expected})")
print("\nTesting Postfix Evaluation:")
test_cases = [
("2 3 +", 5.0),
("2 3 + 4 *", 20.0),
("5 1 2 + 4 * + 3 -", 14.0),
("2 3 ^", 8.0),
]
for postfix, expected in test_cases:
result = evaluator.evaluate_postfix(postfix)
status = "✓" if abs(result - expected) < 0.001 else "✗"
print(f" {status} {postfix:20} = {result:10.2f} (expected: {expected})")
print("\nTesting Prefix Evaluation:")
test_cases = [
("+ 2 3", 5.0),
("* + 2 3 4", 20.0),
("- + * + 5 1 2 4 3", 14.0),
]
for prefix, expected in test_cases:
result = evaluator.evaluate_prefix(prefix)
status = "✓" if abs(result - expected) < 0.001 else "✗"
print(f" {status} {prefix:20} = {result:10.2f} (expected: {expected})")
print("\nTesting Infix Evaluation:")
test_cases = [
("2+3", 5.0),
("2+3*4", 14.0),
("(2+3)*4", 20.0),
("2^3^2", 512.0), # Right associative: 2^(3^2) = 2^9
("10%3", 1.0),
]
for infix, expected in test_cases:
result = evaluator.evaluate_infix(infix)
status = "✓" if abs(result - expected) < 0.001 else "✗"
print(f" {status} {infix:20} = {result:10.2f} (expected: {expected})")
9.9 Complete Implementations - Topic 41: Balanced Parentheses
Topic 41: Multiple Solution Approaches for Balanced Parentheses
class ParenthesesValidator:
"""
Complete solution suite for balanced parentheses problems
Supports:
- Basic balanced parentheses
- Multiple bracket types
- Minimum removals to balance
- Generate all balanced combinations
- Valid parentheses substring
"""
def is_balanced_basic(self, s):
"""
Check if parentheses are balanced (single type)
Args:
s: String containing parentheses
Returns:
True if balanced, False otherwise
Algorithm:
Use counter: +1 for '(', -1 for ')'
Never go negative, end at 0
Time: O(n), Space: O(1)
Examples:
"()" -> True
"((()))" -> True
"())(" -> False
"""
counter = 0
for char in s:
if char == '(':
counter += 1
elif char == ')':
counter -= 1
# If counter goes negative, more ')' than '('
if counter < 0:
return False
# Must end with counter = 0
return counter == 0
def is_balanced_stack(self, s):
"""
Check if parentheses are balanced (multiple types)
Args:
s: String containing (), {}, []
Returns:
True if balanced, False otherwise
Algorithm:
1. Use stack
2. Push opening brackets
3. Pop and match closing brackets
4. Stack empty at end
Time: O(n), Space: O(n)
Examples:
"()[]{}" -> True
"([{}])" -> True
"([)]" -> False
"""
stack = []
pairs = {'(': ')', '{': '}', '[': ']'}
opening = set(pairs.keys())
closing = set(pairs.values())
for char in s:
if char in opening:
stack.append(char)
elif char in closing:
if not stack:
return False
# Check if top matches
if pairs[stack[-1]] != char:
return False
stack.pop()
return len(stack) == 0
def min_remove_to_balance(self, s):
"""
Find minimum removals to make parentheses balanced
Args:
s: String with parentheses
Returns:
String with minimum characters removed
Algorithm:
1. First pass: mark invalid ')'
2. Second pass: mark invalid '('
3. Build result excluding marked
Time: O(n), Space: O(n)
Examples:
"lee(t(c)o)de)" -> "lee(t(c)o)de"
"a)b(c)d" -> "ab(c)d"
"))((" -> ""
"""
to_remove = set()
stack = []
# First pass: mark unmatched ')'
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == ')':
if stack:
stack.pop()
else:
to_remove.add(i)
# Second pass: mark unmatched '('
to_remove.update(stack)
# Build result
result = []
for i, char in enumerate(s):
if i not in to_remove:
result.append(char)
return ''.join(result)
def generate_balanced(self, n):
"""
Generate all valid balanced parentheses
Args:
n: Number of pairs
Returns:
List of all valid combinations
Algorithm:
Backtracking with constraints:
- Can add '(' if open_count < n
- Can add ')' if close_count < open_count
Time: O(4^n / sqrt(n)), Space: O(n)
Examples:
n=1 -> ["()"]
n=2 -> ["(())", "()()"]
n=3 -> ["((()))", "(()())", "(())()", "()(())", "()()()"]
"""
result = []
def backtrack(current, open_count, close_count):
# Base case: generated n pairs
if len(current) == 2 * n:
result.append(current)
return
# Add '(' if we can
if open_count < n:
backtrack(current + '(', open_count + 1, close_count)
# Add ')' if we can
if close_count < open_count:
backtrack(current + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
def longest_valid_length(self, s):
"""
Find length of longest valid parentheses substring
Args:
s: String containing parentheses
Returns:
Length of longest valid substring
Algorithm:
Use stack with indices
Track last invalid position
Time: O(n), Space: O(n)
Examples:
"(()" -> 2
")()())" -> 4
"" -> 0
"""
stack = [-1] # Initialize with base
max_length = 0
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
# No matching '(', update base
stack.append(i)
else:
# Calculate length
max_length = max(max_length, i - stack[-1])
return max_length
def score_balanced(self, s):
"""
Score balanced parentheses
Rules:
() = 1
AB = A + B (concatenation)
(A) = 2 * A (nesting)
Args:
s: Balanced parentheses string
Returns:
Score value
Algorithm:
Use stack to track scores at each level
Time: O(n), Space: O(n)
Examples:
"()" -> 1
"(())" -> 2
"()()" -> 2
"(()(()))" -> 6
"""
stack = [0] # Initialize with base score
for char in s:
if char == '(':
# Start new level
stack.append(0)
else:
# Close level
top = stack.pop()
score = 1 if top == 0 else 2 * top
stack[-1] += score
return stack[0]
def is_valid_with_wildcards(self, s):
"""
Check if valid with wildcards
'*' can be '(', ')', or empty
Args:
s: String with '(', ')', '*'
Returns:
True if can be made valid
Algorithm:
Track range of possible open brackets
- low: minimum possible
- high: maximum possible
Time: O(n), Space: O(1)
Examples:
"(*)" -> True
"(*()))" -> True
"()))((" -> False
"""
low = 0 # Min possible '('
high = 0 # Max possible '('
for char in s:
if char == '(':
low += 1
high += 1
elif char == ')':
low -= 1
high -= 1
else: # '*'
low -= 1 # Treat as ')'
high += 1 # Treat as '('
# Can't have more ')' than '('
if high < 0:
return False
# low should never be negative
low = max(low, 0)
return low == 0
# Comprehensive test cases for Topic 41
def test_parentheses_validation():
"""Test all parentheses validation methods"""
validator = ParenthesesValidator()
print("Testing basic balanced check:")
test_cases = [
("()", True),
("((()))", True),
("())(", False),
("", True),
]
for s, expected in test_cases:
result = validator.is_balanced_basic(s)
status = "✓" if result == expected else "✗"
print(f" {status} '{s:15}' -> {result} (expected: {expected})")
print("\nTesting stack-based balanced check:")
test_cases = [
("()[]{}", True),
("([{}])", True),
("([)]", False),
("{[()]}", True),
]
for s, expected in test_cases:
result = validator.is_balanced_stack(s)
status = "✓" if result == expected else "✗"
print(f" {status} '{s:15}' -> {result} (expected: {expected})")
print("\nTesting minimum removals:")
test_cases = [
("lee(t(c)o)de)", "lee(t(c)o)de"),
("a)b(c)d", "ab(c)d"),
("))((", ""),
]
for s, expected in test_cases:
result = validator.min_remove_to_balance(s)
status = "✓" if result == expected else "✗"
print(f" {status} '{s:15}' -> '{result}' (expected: '{expected}')")
print("\nTesting generate balanced:")
for n in [1, 2, 3]:
result = validator.generate_balanced(n)
print(f" n={n}: {result}")
print("\nTesting longest valid length:")
test_cases = [
("(()", 2),
(")()())", 4),
("", 0),
("()()", 4),
]
for s, expected in test_cases:
result = validator.longest_valid_length(s)
status = "✓" if result == expected else "✗"
print(f" {status} '{s:15}' -> {result} (expected: {expected})")
print("\nTesting score calculation:")
test_cases = [
("()", 1),
("(())", 2),
("()()", 2),
("(()(()))", 6),
]
for s, expected in test_cases:
result = validator.score_balanced(s)
status = "✓" if result == expected else "✗"
print(f" {status} '{s:15}' -> {result} (expected: {expected})")
print("\nTesting wildcards:")
test_cases = [
("(*)", True),
("(*()))", True),
("()))((" , False),
]
for s, expected in test_cases:
result = validator.is_valid_with_wildcards(s)
status = "✓" if result == expected else "✗"
print(f" {status} '{s:15}' -> {result} (expected: {expected})")
9.10 Complete Implementations - Topic 42: Next Greater Element
Topic 42: NGE Variations and Optimizations
class NextGreaterElement:
"""
Complete solution suite for Next Greater Element problems
Variations:
- Basic NGE
- NGE in circular array
- NGE to the left
- NGE for each element in array2 present in array1
- Previous Greater Element
"""
def next_greater_basic(self, arr):
"""
Find next greater element for each element
Args:
arr: Input array
Returns:
Array where result[i] = next greater element or -1
Algorithm:
Monotonic decreasing stack
- Maintain indices in decreasing order of values
- When find larger, pop and set result
Time: O(n), Space: O(n)
Examples:
[4, 5, 2, 10] -> [5, 10, 10, -1]
[13, 7, 6, 12] -> [-1, 12, 12, -1]
"""
n = len(arr)
result = [-1] * n
stack = [] # Store indices
# Process right to left
for i in range(n - 1, -1, -1):
# Pop smaller or equal elements
while stack and arr[stack[-1]] <= arr[i]:
stack.pop()
# Top of stack is next greater
if stack:
result[i] = arr[stack[-1]]
stack.append(i)
return result
def next_greater_circular(self, arr):
"""
Find NGE in circular array
Array is circular: arr[n-1] wraps to arr[0]
Args:
arr: Input array
Returns:
NGE for each element considering circular nature
Algorithm:
Process array twice (2n elements)
Use modulo for indices
Time: O(n), Space: O(n)
Examples:
[1, 2, 1] -> [2, -1, 2]
[1, 2, 3, 4, 3] -> [2, 3, 4, -1, 4]
"""
n = len(arr)
result = [-1] * n
stack = []
# Process array twice
for i in range(2 * n - 1, -1, -1):
idx = i % n
# Pop smaller or equal
while stack and stack[-1] <= arr[idx]:
stack.pop()
# Only set result on first pass
if i < n and stack:
result[idx] = stack[-1]
stack.append(arr[idx])
return result
def next_greater_left(self, arr):
"""
Find next greater element to the left
Args:
arr: Input array
Returns:
Array where result[i] = next greater to left or -1
Algorithm:
Similar to basic NGE but scan left to right
Time: O(n), Space: O(n)
Examples:
[4, 5, 2, 10] -> [-1, -1, 5, -1]
[1, 3, 2, 4] -> [-1, -1, 3, -1]
"""
n = len(arr)
result = [-1] * n
stack = []
for i in range(n):
# Pop smaller or equal
while stack and arr[stack[-1]] <= arr[i]:
stack.pop()
# Top is NGE to left
if stack:
result[i] = arr[stack[-1]]
stack.append(i)
return result
def next_greater_map(self, arr1, arr2):
"""
Find NGE for elements in arr1 that appear in arr2
Args:
arr1: Query array (subset of arr2)
arr2: Full array
Returns:
NGE for each element in arr1 based on arr2
Algorithm:
1. Find NGE for all elements in arr2
2. Map results for arr1 elements
Time: O(n + m), Space: O(n)
Examples:
arr1=[4,1,2], arr2=[1,3,4,2]
-> [-1,3,-1] (4->-1, 1->3, 2->-1)
"""
# Build NGE map for arr2
nge_map = {}
stack = []
for num in arr2:
# Pop smaller elements and set their NGE
while stack and stack[-1] < num:
nge_map[stack.pop()] = num
stack.append(num)
# Remaining have no NGE
while stack:
nge_map[stack.pop()] = -1
# Map to arr1
return [nge_map[num] for num in arr1]
def previous_greater(self, arr):
"""
Find previous greater element for each element
Args:
arr: Input array
Returns:
Array where result[i] = previous greater or -1
Algorithm:
Monotonic decreasing stack from left
Time: O(n), Space: O(n)
Examples:
[4, 5, 2, 10] -> [-1, -1, 5, -1]
[10, 4, 2, 20, 40] -> [-1, 10, 4, -1, -1]
"""
n = len(arr)
result = [-1] * n
stack = []
for i in range(n):
# Pop smaller or equal
while stack and arr[stack[-1]] <= arr[i]:
stack.pop()
# Top is previous greater
if stack:
result[i] = arr[stack[-1]]
stack.append(i)
return result
def next_smaller(self, arr):
"""
Find next smaller element for each element
Args:
arr: Input array
Returns:
Array where result[i] = next smaller or -1
Algorithm:
Monotonic increasing stack
Time: O(n), Space: O(n)
Examples:
[4, 5, 2, 10] -> [2, 2, -1, -1]
[4, 2, 1, 5] -> [2, 1, -1, -1]
"""
n = len(arr)
result = [-1] * n
stack = []
for i in range(n - 1, -1, -1):
# Pop larger or equal
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
# Top is next smaller
if stack:
result[i] = arr[stack[-1]]
stack.append(i)
return result
def count_nge(self, arr):
"""
Count number of greater elements to the right
Args:
arr: Input array
Returns:
Array where result[i] = count of elements > arr[i] to right
Algorithm:
For each element, count elements popped from stack
Time: O(n), Space: O(n)
Examples:
[3, 4, 2, 7, 5] -> [3, 2, 2, 0, 0]
"""
n = len(arr)
result = [0] * n
stack = []
for i in range(n):
count = 0
# Pop and count smaller elements
while stack and arr[stack[-1]] < arr[i]:
idx = stack.pop()
result[idx] = result[i] + count + 1
count += 1
stack.append(i)
return result
# Comprehensive test cases for Topic 42
def test_next_greater_element():
"""Test all NGE variations"""
nge = NextGreaterElement()
print("Testing basic NGE:")
test_cases = [
([4, 5, 2, 10], [5, 10, 10, -1]),
([13, 7, 6, 12], [-1, 12, 12, -1]),
([1, 2, 3, 4], [2, 3, 4, -1]),
]
for arr, expected in test_cases:
result = nge.next_greater_basic(arr)
status = "✓" if result == expected else "✗"
print(f" {status} {arr} -> {result}")
print("\nTesting circular NGE:")
test_cases = [
([1, 2, 1], [2, -1, 2]),
([1, 2, 3, 4, 3], [2, 3, 4, -1, 4]),
]
for arr, expected in test_cases:
result = nge.next_greater_circular(arr)
status = "✓" if result == expected else "✗"
print(f" {status} {arr} -> {result}")
print("\nTesting NGE to left:")
test_cases = [
([4, 5, 2, 10], [-1, -1, 5, -1]),
([1, 3, 2, 4], [-1, -1, 3, -1]),
]
for arr, expected in test_cases:
result = nge.next_greater_left(arr)
status = "✓" if result == expected else "✗"
print(f" {status} {arr} -> {result}")
print("\nTesting NGE with mapping:")
arr1 = [4, 1, 2]
arr2 = [1, 3, 4, 2]
result = nge.next_greater_map(arr1, arr2)
print(f" arr1={arr1}, arr2={arr2}")
print(f" Result: {result}")
print("\nTesting previous greater:")
test_cases = [
([4, 5, 2, 10], [-1, -1, 5, -1]),
([10, 4, 2, 20, 40], [-1, 10, 4, -1, -1]),
]
for arr, expected in test_cases:
result = nge.previous_greater(arr)
status = "✓" if result == expected else "✗"
print(f" {status} {arr} -> {result}")
print("\nTesting next smaller:")
test_cases = [
([4, 5, 2, 10], [2, 2, -1, -1]),
([4, 2, 1, 5], [2, 1, -1, -1]),
]
for arr, expected in test_cases:
result = nge.next_smaller(arr)
status = "✓" if result == expected else "✗"
print(f" {status} {arr} -> {result}")
9.11 Complete Implementations - Topic 43: Stock Span Problem
Topic 43: Stock Span with Multiple Approaches
class StockSpan:
"""
Complete solution suite for Stock Span Problem
Variations:
- Basic stock span
- Online stock span (streaming)
- Stock span with queries
- Maximum span in range
"""
def stock_span_basic(self, prices):
"""
Calculate span for each day
Span: number of consecutive days (including current)
where price <= current price
Args:
prices: Array of stock prices
Returns:
Array of spans
Algorithm:
Monotonic decreasing stack
- Store indices of prices
- Pop while current price >= stack top
Time: O(n), Space: O(n)
Examples:
[100, 80, 60, 70, 60, 75, 85]
-> [1, 1, 1, 2, 1, 4, 6]
"""
n = len(prices)
spans = [0] * n
stack = [] # Store indices
for i in range(n):
# Pop smaller or equal prices
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
# Span is distance to previous greater
if not stack:
spans[i] = i + 1 # All previous days
else:
spans[i] = i - stack[-1]
stack.append(i)
return spans
def stock_span_brute_force(self, prices):
"""
Brute force approach for comparison
Args:
prices: Array of stock prices
Returns:
Array of spans
Time: O(n²), Space: O(1)
"""
n = len(prices)
spans = [0] * n
for i in range(n):
span = 1
j = i - 1
# Count consecutive days with price <= current
while j >= 0 and prices[j] <= prices[i]:
span += 1
j -= 1
spans[i] = span
return spans
class StockSpanner:
"""
Online stock spanner for streaming prices
Efficiently handles one price at a time
"""
def __init__(self):
"""Initialize with empty stack"""
self.stack = [] # (price, span) pairs
def next(self, price):
"""
Process next price and return its span
Args:
price: Current stock price
Returns:
Span for current price
Algorithm:
Maintain stack of (price, span) pairs
- Accumulate spans while popping
- Each element popped once
Time: O(1) amortized, Space: O(n)
Example:
StockSpanner().next(100) = 1
StockSpanner().next(80) = 1
StockSpanner().next(60) = 1
StockSpanner().next(70) = 2
StockSpanner().next(60) = 1
StockSpanner().next(75) = 4
StockSpanner().next(85) = 6
"""
span = 1
# Pop all with price <= current
while self.stack and self.stack[-1][0] <= price:
# Accumulate spans
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
def reset(self):
"""Reset the spanner"""
self.stack.clear()
class AdvancedStockSpan:
"""
Advanced stock span operations
"""
def max_span_in_range(self, prices, queries):
"""
Find maximum span in given ranges
Args:
prices: Array of stock prices
queries: List of (left, right) ranges
Returns:
Maximum span in each range
Algorithm:
Precompute spans, then query using segment tree
Time: O(n + q), Space: O(n)
Example:
prices = [100, 80, 60, 70, 60, 75, 85]
queries = [(0, 3), (2, 6)]
-> [2, 6]
"""
# First get all spans
spans = self._compute_spans(prices)
# Answer queries
results = []
for left, right in queries:
max_span = max(spans[left:right+1])
results.append(max_span)
return results
def _compute_spans(self, prices):
"""Helper to compute spans"""
n = len(prices)
spans = [0] * n
stack = []
for i in range(n):
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
spans[i] = i + 1 if not stack else i - stack[-1]
stack.append(i)
return spans
def total_span(self, prices):
"""
Calculate total of all spans
Args:
prices: Array of stock prices
Returns:
Sum of all spans
Algorithm:
Compute spans and sum
Time: O(n), Space: O(n)
Example:
[100, 80, 60, 70, 60, 75, 85]
Spans: [1, 1, 1, 2, 1, 4, 6]
Total: 16
"""
spans = self._compute_spans(prices)
return sum(spans)
def span_product(self, prices):
"""
Calculate span * price for each day
Args:
prices: Array of stock prices
Returns:
Array of span * price values
Algorithm:
Compute spans, multiply by prices
Time: O(n), Space: O(n)
Example:
prices = [10, 20, 15, 25]
spans = [1, 2, 1, 4]
result = [10, 40, 15, 100]
"""
spans = self._compute_spans(prices)
return [span * price for span, price in zip(spans, prices)]
# Comprehensive test cases for Topic 43
def test_stock_span():
"""Test all stock span methods"""
print("Testing basic stock span:")
prices = [100, 80, 60, 70, 60, 75, 85]
expected = [1, 1, 1, 2, 1, 4, 6]
span = StockSpan()
result = span.stock_span_basic(prices)
status = "✓" if result == expected else "✗"
print(f" {status} Optimized: {result}")
result_brute = span.stock_span_brute_force(prices)
status = "✓" if result_brute == expected else "✗"
print(f" {status} Brute force: {result_brute}")
print("\nTesting online stock spanner:")
spanner = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
expected = [1, 1, 1, 2, 1, 4, 6]
results = []
for price in prices:
results.append(spanner.next(price))
status = "✓" if results == expected else "✗"
print(f" {status} Online: {results}")
print("\nTesting advanced operations:")
adv = AdvancedStockSpan()
prices = [100, 80, 60, 70, 60, 75, 85]
queries = [(0, 3), (2, 6)]
max_spans = adv.max_span_in_range(prices, queries)
print(f" Max spans in ranges: {max_spans}")
total = adv.total_span(prices)
print(f" Total span: {total}")
products = adv.span_product(prices)
print(f" Span products: {products}")
9.12 Complete Implementations - Topic 44: Min Stack
Topic 44: Multiple Min Stack Strategies
class MinStack1:
"""
Min Stack using auxiliary stack
Approach: Keep separate stack for minimums
Space: O(n) in worst case
Every push/pop updates min stack
"""
def __init__(self):
"""Initialize two stacks"""
self.stack = []
self.min_stack = []
def push(self, val):
"""
O(1) - Push value and update min
Always push to main stack
Push to min stack if new minimum
"""
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
"""
O(1) - Pop value and update min
Pop from main stack
Pop from min stack if it's the minimum
"""
if not self.stack:
raise IndexError("Stack is empty")
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
"""O(1) - Get top value"""
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1]
def getMin(self):
"""O(1) - Get minimum value"""
if not self.min_stack:
raise IndexError("Stack is empty")
return self.min_stack[-1]
class MinStack2:
"""
Min Stack using single stack with pairs
Approach: Store (value, min_so_far) pairs
Space: O(2n) = O(n)
Each element knows minimum up to that point
"""
def __init__(self):
"""Initialize single stack"""
self.stack = []
def push(self, val):
"""
O(1) - Push (value, minimum) pair
Minimum is min of val and previous minimum
"""
if not self.stack:
self.stack.append((val, val))
else:
current_min = min(val, self.stack[-1][1])
self.stack.append((val, current_min))
def pop(self):
"""O(1) - Pop and return value"""
if not self.stack:
raise IndexError("Stack is empty")
return self.stack.pop()[0]
def top(self):
"""O(1) - Get top value"""
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1][0]
def getMin(self):
"""O(1) - Get minimum"""
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1][1]
class MinStack3:
"""
Min Stack using difference approach
Approach: Store differences from minimum
Space: O(n), but saves space in practice
Clever encoding to track minimum changes
"""
def __init__(self):
"""Initialize stack and min tracker"""
self.stack = []
self.min_val = None
def push(self, val):
"""
O(1) - Push using difference encoding
If val < min: push difference, update min
Else: push val normally
"""
if not self.stack:
self.stack.append(val)
self.min_val = val
else:
if val < self.min_val:
# Push encoded difference
self.stack.append(2 * val - self.min_val)
self.min_val = val
else:
self.stack.append(val)
def pop(self):
"""
O(1) - Pop and decode if needed
If top < min: restore previous min
"""
if not self.stack:
raise IndexError("Stack is empty")
top = self.stack.pop()
if top < self.min_val:
# Restore previous minimum
old_min = self.min_val
self.min_val = 2 * self.min_val - top
return old_min
else:
return top
def top(self):
"""O(1) - Get top (decode if needed)"""
if not self.stack:
raise IndexError("Stack is empty")
top = self.stack[-1]
return self.min_val if top < self.min_val else top
def getMin(self):
"""O(1) - Get minimum"""
if self.min_val is None:
raise IndexError("Stack is empty")
return self.min_val
class MinMaxStack:
"""
Stack with both min and max in O(1)
Extends min stack concept to track maximum too
"""
def __init__(self):
"""Initialize with min and max stacks"""
self.stack = []
self.min_stack = []
self.max_stack = []
def push(self, val):
"""O(1) - Push and update min/max"""
self.stack.append(val)
# Update min stack
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
# Update max stack
if not self.max_stack or val >= self.max_stack[-1]:
self.max_stack.append(val)
def pop(self):
"""O(1) - Pop and update min/max"""
if not self.stack:
raise IndexError("Stack is empty")
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
if val == self.max_stack[-1]:
self.max_stack.pop()
return val
def top(self):
"""O(1) - Get top"""
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1]
def getMin(self):
"""O(1) - Get minimum"""
if not self.min_stack:
raise IndexError("Stack is empty")
return self.min_stack[-1]
def getMax(self):
"""O(1) - Get maximum"""
if not self.max_stack:
raise IndexError("Stack is empty")
return self.max_stack[-1]
# Comprehensive test cases for Topic 44
def test_min_stack():
"""Test all min stack implementations"""
print("Testing MinStack1 (auxiliary stack):")
stack = MinStack1()
operations = [
("push", -2), ("push", 0), ("push", -3),
("getMin", None), ("pop", None), ("top", None), ("getMin", None)
]
expected = [None, None, None, -3, -3, 0, -2]
results = []
for op, val in operations:
if op == "push":
stack.push(val)
results.append(None)
elif op == "pop":
results.append(stack.pop())
elif op == "top":
results.append(stack.top())
elif op == "getMin":
results.append(stack.getMin())
status = "✓" if results == expected else "✗"
print(f" {status} Results: {results}")
print("\nTesting MinStack2 (pairs):")
stack = MinStack2()
for op, val in operations:
if op == "push":
stack.push(val)
elif op == "pop":
stack.pop()
elif op == "top":
stack.top()
elif op == "getMin":
stack.getMin()
print(" ✓ MinStack2 works correctly")
print("\nTesting MinStack3 (difference):")
stack = MinStack3()
for op, val in operations:
if op == "push":
stack.push(val)
elif op == "pop":
stack.pop()
elif op == "top":
stack.top()
elif op == "getMin":
stack.getMin()
print(" ✓ MinStack3 works correctly")
print("\nTesting MinMaxStack:")
stack = MinMaxStack()
stack.push(5)
stack.push(2)
stack.push(8)
stack.push(1)
print(f" Min: {stack.getMin()}, Max: {stack.getMax()}")
stack.pop()
print(f" After pop - Min: {stack.getMin()}, Max: {stack.getMax()}")
9.13 Complete Implementations - Topic 45: Queue using Stacks
Topic 45: Queue Implementation with Stacks
class QueueUsingTwoStacks:
"""
Queue using two stacks - Most efficient approach
Approach:
- in_stack: for enqueue operations
- out_stack: for dequeue operations
- Transfer only when out_stack is empty
Time Complexity:
- enqueue: O(1)
- dequeue: O(1) amortized
- peek: O(1) amortized
"""
def __init__(self):
"""Initialize two stacks"""
self.in_stack = []
self.out_stack = []
def enqueue(self, item):
"""
O(1) - Add to back of queue
Always push to in_stack
"""
self.in_stack.append(item)
def dequeue(self):
"""
O(1) amortized - Remove from front
Transfer from in_stack to out_stack if needed
Each element moves at most twice
"""
self._transfer_if_needed()
if not self.out_stack:
raise IndexError("Queue is empty")
return self.out_stack.pop()
def peek(self):
"""
O(1) amortized - View front element
Transfer if needed, then peek at out_stack top
"""
self._transfer_if_needed()
if not self.out_stack:
raise IndexError("Queue is empty")
return self.out_stack[-1]
def is_empty(self):
"""O(1) - Check if queue is empty"""
return len(self.in_stack) == 0 and len(self.out_stack) == 0
def size(self):
"""O(1) - Get queue size"""
return len(self.in_stack) + len(self.out_stack)
def _transfer_if_needed(self):
"""
Transfer elements from in_stack to out_stack
Only transfer when out_stack is empty
Reverses order: LIFO -> FIFO
"""
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
class QueueUsingOneStack:
"""
Queue using one stack - Less efficient but interesting
Approach:
- Use recursion for dequeue
- Recursively pop to bottom, then restore
Time Complexity:
- enqueue: O(1)
- dequeue: O(n)
"""
def __init__(self):
"""Initialize single stack"""
self.stack = []
def enqueue(self, item):
"""O(1) - Push to stack"""
self.stack.append(item)
def dequeue(self):
"""
O(n) - Remove front element using recursion
Recursively pop until reaching bottom
"""
if not self.stack:
raise IndexError("Queue is empty")
if len(self.stack) == 1:
return self.stack.pop()
# Pop top element
temp = self.stack.pop()
# Recursive dequeue
result = self.dequeue()
# Restore popped element
self.stack.append(temp)
return result
def peek(self):
"""O(n) - View front element"""
if not self.stack:
raise IndexError("Queue is empty")
if len(self.stack) == 1:
return self.stack[-1]
temp = self.stack.pop()
result = self.peek()
self.stack.append(temp)
return result
def is_empty(self):
"""O(1) - Check if empty"""
return len(self.stack) == 0
class QueueWithHelper:
"""
Queue using stack with helper stack for each dequeue
Approach:
- Use helper stack to reverse elements
- Transfer back after dequeue
Time Complexity:
- enqueue: O(1)
- dequeue: O(n) worst case
"""
def __init__(self):
"""Initialize main and helper stack"""
self.main_stack = []
self.helper_stack = []
def enqueue(self, item):
"""O(1) - Add to main stack"""
self.main_stack.append(item)
def dequeue(self):
"""
O(n) - Remove front using helper
Transfer all to helper, pop bottom, transfer back
"""
if not self.main_stack:
raise IndexError("Queue is empty")
# Transfer all to helper
while len(self.main_stack) > 1:
self.helper_stack.append(self.main_stack.pop())
# Get front element
result = self.main_stack.pop()
# Transfer back
while self.helper_stack:
self.main_stack.append(self.helper_stack.pop())
return result
def peek(self):
"""O(n) - View front using helper"""
if not self.main_stack:
raise IndexError("Queue is empty")
# Transfer all to helper
while len(self.main_stack) > 1:
self.helper_stack.append(self.main_stack.pop())
# Peek at front
result = self.main_stack[-1]
# Transfer back
while self.helper_stack:
self.main_stack.append(self.helper_stack.pop())
return result
class EfficientQueueBenchmark:
"""
Compare performance of different implementations
"""
def __init__(self):
"""Initialize test data"""
self.operations = 1000
def benchmark_two_stacks(self):
"""Benchmark two-stack implementation"""
import time
queue = QueueUsingTwoStacks()
start = time.time()
# Mix of enqueue and dequeue
for i in range(self.operations):
queue.enqueue(i)
for i in range(self.operations // 2):
queue.dequeue()
for i in range(self.operations // 2):
queue.enqueue(i)
while not queue.is_empty():
queue.dequeue()
elapsed = time.time() - start
return elapsed
def benchmark_one_stack(self):
"""Benchmark one-stack implementation"""
import time
queue = QueueUsingOneStack()
start = time.time()
# Fewer operations due to O(n) dequeue
ops = min(100, self.operations // 10)
for i in range(ops):
queue.enqueue(i)
for i in range(ops // 2):
queue.dequeue()
elapsed = time.time() - start
return elapsed
# Comprehensive test cases for Topic 45
def test_queue_using_stacks():
"""Test all queue implementations"""
print("Testing QueueUsingTwoStacks:")
queue = QueueUsingTwoStacks()
# Enqueue elements
for i in range(1, 6):
queue.enqueue(i)
print(f" After enqueuing 1-5: size={queue.size()}")
# Dequeue and peek
print(f" Peek front: {queue.peek()}")
print(f" Dequeue: {queue.dequeue()}")
print(f" Dequeue: {queue.dequeue()}")
print(f" Peek front: {queue.peek()}")
# More enqueue
queue.enqueue(6)
queue.enqueue(7)
# Dequeue all
result = []
while not queue.is_empty():
result.append(queue.dequeue())
print(f" Final dequeue order: {result}")
print("\nTesting QueueUsingOneStack:")
queue = QueueUsingOneStack()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(f" Peek: {queue.peek()}")
print(f" Dequeue: {queue.dequeue()}")
print(f" Dequeue: {queue.dequeue()}")
print(f" Dequeue: {queue.dequeue()}")
print("\nTesting QueueWithHelper:")
queue = QueueWithHelper()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(f" Peek: {queue.peek()}")
print(f" Dequeue: {queue.dequeue()}")
print("\nPerformance Comparison:")
benchmark = EfficientQueueBenchmark()
time_two = benchmark.benchmark_two_stacks()
print(f" Two stacks: {time_two:.4f}s")
time_one = benchmark.benchmark_one_stack()
print(f" One stack: {time_one:.4f}s")
print(f" Speedup: {time_one/time_two:.2f}x")
9.14 Complete Implementations - Topic 46: Monotonic Stack
Topic 46: Comprehensive Monotonic Stack Coverage
class MonotonicStack:
"""
Complete monotonic stack patterns and applications
Types:
- Monotonic Increasing: each element >= previous
- Monotonic Decreasing: each element <= previous
- Strictly Monotonic: strict inequality
"""
def monotonic_increasing(self, arr):
"""
Build monotonically increasing stack
Args:
arr: Input array
Returns:
Indices in monotonically increasing order
Algorithm:
Pop all elements >= current before pushing
Example:
[3, 1, 4, 1, 5, 9, 2, 6]
Stack progres: [3], [1], [1,4], [1], [1,5], [1,5,9], [1,2], [1,2,6]
"""
stack = []
process_log = []
for i, val in enumerate(arr):
# Pop elements >= current (maintain strict increasing)
while stack and arr[stack[-1]] >= val:
stack.pop()
stack.append(i)
process_log.append((val, [arr[j] for j in stack]))
return stack, process_log
def monotonic_decreasing(self, arr):
"""
Build monotonically decreasing stack
Args:
arr: Input array
Returns:
Indices in monotonically decreasing order
Algorithm:
Pop all elements <= current before pushing
Example:
[3, 1, 4, 1, 5, 9, 2, 6]
Stack progress: [3], [3,1], [4], [4,1], [5], [9], [9,2], [9,6]
"""
stack = []
process_log = []
for i, val in enumerate(arr):
# Pop elements <= current (maintain strict decreasing)
while stack and arr[stack[-1]] <= val:
stack.pop()
stack.append(i)
process_log.append((val, [arr[j] for j in stack]))
return stack, process_log
def largest_rectangle_histogram(self, heights):
"""
Find largest rectangle in histogram
Args:
heights: Array of bar heights
Returns:
Maximum rectangle area
Algorithm:
Use monotonic increasing stack
- Pop when current < stack top
- Calculate area using popped height
- Width = distance between neighbors
Time: O(n), Space: O(n)
Example:
heights = [2, 1, 5, 6, 2, 3]
max area = 10 (height=5, width=2)
"""
stack = []
max_area = 0
index = 0
while index < len(heights):
# If current bar higher, push
if not stack or heights[index] >= heights[stack[-1]]:
stack.append(index)
index += 1
else:
# Pop and calculate area
top = stack.pop()
height = heights[top]
# Width calculation
if not stack:
width = index
else:
width = index - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
# Process remaining bars
while stack:
top = stack.pop()
height = heights[top]
if not stack:
width = index
else:
width = index - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
return max_area
def trapping_rain_water(self, height):
"""
Calculate trapped rain water
Args:
height: Elevation map
Returns:
Units of water trapped
Algorithm:
Use stack to track potential water containers
When find higher bar, calculate trapped water
Time: O(n), Space: O(n)
Example:
[0,1,0,2,1,0,1,3,2,1,2,1]
Water trapped = 6
"""
stack = []
water = 0
for i, h in enumerate(height):
# Pop bars shorter than current
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
# Calculate trapped water
bounded_height = min(height[stack[-1]], h) - height[bottom]
width = i - stack[-1] - 1
water += bounded_height * width
stack.append(i)
return water
def daily_temperatures(self, temperatures):
"""
Find days until warmer temperature
Args:
temperatures: Daily temperatures
Returns:
Days to wait for warmer temp
Algorithm:
Monotonic decreasing stack
Pop when find higher temperature
Time: O(n), Space: O(n)
Example:
[73, 74, 75, 71, 69, 72, 76, 73]
[1, 1, 4, 2, 1, 1, 0, 0]
"""
n = len(temperatures)
result = [0] * n
stack = []
for i, temp in enumerate(temperatures):
# Pop cooler days
while stack and temperatures[stack[-1]] < temp:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx
stack.append(i)
return result
def remove_k_digits(self, num, k):
"""
Remove k digits to get smallest number
Args:
num: Number as string
k: Digits to remove
Returns:
Smallest possible number
Algorithm:
Monotonic increasing stack
Remove larger digits greedily
Time: O(n), Space: O(n)
Example:
num="1432219", k=3 -> "1219"
num="10200", k=1 -> "200"
"""
stack = []
for digit in num:
# Remove larger digits
while stack and k > 0 and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# Remove remaining k digits from end
while k > 0:
stack.pop()
k -= 1
# Build result, remove leading zeros
result = ''.join(stack).lstrip('0')
return result if result else '0'
def sum_subarray_minimums(self, arr):
"""
Sum of minimums of all subarrays
Args:
arr: Input array
Returns:
Sum of all subarray minimums
Algorithm:
For each element, find range where it's minimum
Use two monotonic stacks (left and right)
Time: O(n), Space: O(n)
Example:
[3, 1, 2, 4]
Minimums: [3,1,1,4] + [1,1,2] + [1,2] + [1]
Sum = 17
"""
MOD = 10**9 + 7
n = len(arr)
# Find previous less element
left = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
# Find next less element
right = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
# Calculate sum
result = 0
for i in range(n):
# Number of subarrays with arr[i] as minimum
left_count = i - left[i]
right_count = right[i] - i
result += arr[i] * left_count * right_count
result %= MOD
return result
# Comprehensive test cases for Topic 46
def test_monotonic_stack():
"""Test all monotonic stack applications"""
mono = MonotonicStack()
print("Testing monotonic increasing:")
arr = [3, 1, 4, 1, 5, 9, 2, 6]
indices, log = mono.monotonic_increasing(arr)
print(f" Final stack values: {[arr[i] for i in indices]}")
print("\nTesting monotonic decreasing:")
indices, log = mono.monotonic_decreasing(arr)
print(f" Final stack values: {[arr[i] for i in indices]}")
print("\nTesting largest rectangle:")
heights = [2, 1, 5, 6, 2, 3]
area = mono.largest_rectangle_histogram(heights)
print(f" Heights: {heights}")
print(f" Max area: {area}")
print("\nTesting rain water:")
elevation = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
water = mono.trapping_rain_water(elevation)
print(f" Elevation: {elevation}")
print(f" Water trapped: {water}")
print("\nTesting daily temperatures:")
temps = [73, 74, 75, 71, 69, 72, 76, 73]
days = mono.daily_temperatures(temps)
print(f" Temperatures: {temps}")
print(f" Days to wait: {days}")
print("\nTesting remove k digits:")
test_cases = [
("1432219", 3, "1219"),
("10200", 1, "200"),
("10", 2, "0"),
]
for num, k, expected in test_cases:
result = mono.remove_k_digits(num, k)
status = "✓" if result == expected else "✗"
print(f" {status} remove {k} from '{num}' -> '{result}' (expected: '{expected}')")
print("\nTesting subarray minimums sum:")
arr = [3, 1, 2, 4]
total = mono.sum_subarray_minimums(arr)
print(f" Array: {arr}")
print(f" Sum of minimums: {total}")
9.15 Complete Implementations - Topic 47: Backtracking with Stack
Topic 47: Backtracking Patterns using Stacks
class BacktrackingWithStack:
"""
Complete backtracking patterns using explicit stacks
Advantages over recursion:
- No stack overflow risk
- Better control over state
- Easier to visualize/debug
- Can pause/resume execution
"""
def generate_permutations(self, nums):
"""
Generate all permutations using stack
Args:
nums: List of numbers
Returns:
List of all permutations
Algorithm:
Use stack to track (current_perm, remaining_elements)
Pop and explore all choices
Time: O(n! * n), Space: O(n! * n)
Example:
[1, 2, 3] -> [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
"""
result = []
stack = [([], nums)] # (current, remaining)
while stack:
current, remaining = stack.pop()
if not remaining:
result.append(current)
continue
# Try each remaining element
for i in range(len(remaining)):
new_current = current + [remaining[i]]
new_remaining = remaining[:i] + remaining[i+1:]
stack.append((new_current, new_remaining))
return result
def generate_subsets(self, nums):
"""
Generate all subsets using stack
Args:
nums: List of numbers
Returns:
All possible subsets
Algorithm:
Use stack with (current_subset, start_index)
Two choices per element: include or exclude
Time: O(2^n * n), Space: O(2^n * n)
Example:
[1, 2, 3] -> [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
"""
result = []
stack = [([], 0)] # (current, start_index)
while stack:
current, start = stack.pop()
result.append(current[:])
# Try adding each remaining element
for i in range(start, len(nums)):
stack.append((current + [nums[i]], i + 1))
return result
def solve_n_queens(self, n):
"""
Solve N-Queens problem using stack
Args:
n: Board size
Returns:
All valid queen placements
Algorithm:
Use stack with (row, col_placements)
Check validity before pushing
Time: O(n!), Space: O(n^2)
Example:
n=4 -> 2 solutions
"""
def is_valid(placements, row, col):
"""Check if queen placement is safe"""
for r, c in enumerate(placements):
# Same column
if c == col:
return False
# Same diagonal
if abs(r - row) == abs(c - col):
return False
return True
def create_board(placements):
"""Convert placements to board representation"""
board = []
for col in placements:
row = '.' * col + 'Q' + '.' * (n - col - 1)
board.append(row)
return board
result = []
stack = [(0, [])] # (row, column_placements)
while stack:
row, placements = stack.pop()
if row == n:
# Found valid solution
result.append(create_board(placements))
continue
# Try each column in current row
for col in range(n):
if is_valid(placements, row, col):
stack.append((row + 1, placements + [col]))
return result
def word_search(self, board, word):
"""
Find if word exists in board
Args:
board: 2D character grid
word: Word to search
Returns:
True if word found
Algorithm:
Use stack with (row, col, word_index, visited)
Explore 4 directions from each cell
Time: O(m * n * 4^L) where L is word length
Space: O(L)
Example:
board = [['A','B','C'],['S','F','C'],['A','D','E']]
word = "ABCCED" -> True
"""
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
def get_neighbors(r, c):
"""Get valid neighboring cells"""
neighbors = []
for dr, dc in [(0,1), (1,0), (0,-1), (-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
neighbors.append((nr, nc))
return neighbors
# Try starting from each cell
for start_r in range(rows):
for start_c in range(cols):
if board[start_r][start_c] != word[0]:
continue
# Stack: (row, col, word_index, visited_set)
stack = [(start_r, start_c, 0, {(start_r, start_c)})]
while stack:
r, c, idx, visited = stack.pop()
# Found complete word
if idx == len(word) - 1:
return True
# Explore neighbors
for nr, nc in get_neighbors(r, c):
if (nr, nc) not in visited and board[nr][nc] == word[idx + 1]:
new_visited = visited | {(nr, nc)}
stack.append((nr, nc, idx + 1, new_visited))
return False
def combination_sum(self, candidates, target):
"""
Find combinations that sum to target
Args:
candidates: Array of numbers (can reuse)
target: Target sum
Returns:
All combinations that sum to target
Algorithm:
Use stack with (current_combo, remaining_target, start_idx)
Each number can be used multiple times
Time: O(n^(T/M)) where T=target, M=min candidate
Space: O(T/M)
Example:
candidates=[2,3,6,7], target=7
-> [[2,2,3], [7]]
"""
result = []
stack = [([], target, 0)] # (current, remaining, start)
while stack:
current, remaining, start = stack.pop()
if remaining == 0:
result.append(current)
continue
if remaining < 0:
continue
# Try each candidate from start onwards
for i in range(start, len(candidates)):
# Can reuse same candidate
new_combo = current + [candidates[i]]
stack.append((new_combo, remaining - candidates[i], i))
return result
def letter_combinations(self, digits):
"""
Generate letter combinations from phone digits
Args:
digits: String of digits 2-9
Returns:
All possible letter combinations
Algorithm:
Use stack to build combinations
Map each digit to letters
Time: O(4^n * n), Space: O(4^n * n)
Example:
"23" -> ["ad","ae","af","bd","be","bf","cd","ce","cf"]
"""
if not digits:
return []
mapping = {
'2': 'abc', '3': 'def', '4': 'ghi',
'5': 'jkl', '6': 'mno', '7': 'pqrs',
'8': 'tuv', '9': 'wxyz'
}
result = []
stack = [("", 0)] # (current_combo, digit_index)
while stack:
current, idx = stack.pop()
if idx == len(digits):
result.append(current)
continue
# Try each letter for current digit
for letter in mapping[digits[idx]]:
stack.append((current + letter, idx + 1))
return result
# Comprehensive test cases for Topic 47
def test_backtracking_with_stack():
"""Test all backtracking patterns"""
bt = BacktrackingWithStack()
print("Testing permutations:")
perms = bt.generate_permutations([1, 2, 3])
print(f" [1,2,3] has {len(perms)} permutations")
print(f" First few: {perms[:3]}")
print("\nTesting subsets:")
subsets = bt.generate_subsets([1, 2, 3])
print(f" [1,2,3] has {len(subsets)} subsets")
print(f" Subsets: {subsets}")
print("\nTesting N-Queens:")
for n in [4, 5]:
solutions = bt.solve_n_queens(n)
print(f" {n}-Queens has {len(solutions)} solutions")
if solutions:
print(f" First solution:")
for row in solutions[0]:
print(f" {row}")
print("\nTesting word search:")
board = [
['A', 'B', 'C'],
['S', 'F', 'C'],
['A', 'D', 'E']
]
test_words = ["ABCCED", "SEE", "ABCB"]
for word in test_words:
found = bt.word_search(board, word)
print(f" '{word}': {found}")
print("\nTesting combination sum:")
combos = bt.combination_sum([2, 3, 6, 7], 7)
print(f" Target 7 with [2,3,6,7]: {combos}")
print("\nTesting letter combinations:")
letters = bt.letter_combinations("23")
print(f" '23' -> {letters}")
10. Advanced Concepts
10.1 Persistent Stacks
class PersistentStack:
"""
Immutable stack that preserves all versions
Each operation creates new version without modifying old ones
Useful for:
- Version control
- Undo/redo with branching
- Functional programming
"""
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def __init__(self, top=None, size=0):
self._top = top
self._size = size
def push(self, value):
"""O(1) - Create new version with value added"""
new_node = self.Node(value, self._top)
return PersistentStack(new_node, self._size + 1)
def pop(self):
"""O(1) - Create new version with top removed"""
if not self._top:
raise IndexError("Stack is empty")
return PersistentStack(self._top.next, self._size - 1), self._top.value
def peek(self):
"""O(1) - View top value"""
if not self._top:
raise IndexError("Stack is empty")
return self._top.value
def is_empty(self):
"""Check if empty"""
return self._top is None
def size(self):
"""Get size"""
return self._size
def to_list(self):
"""Convert to list (bottom to top)"""
result = []
current = self._top
while current:
result.append(current.value)
current = current.next
return result[::-1]
# Example usage
def persistent_stack_example():
"""
Demonstrate persistent stack
All versions remain accessible
"""
# Version 1: Empty stack
s1 = PersistentStack()
# Version 2: [1]
s2 = s1.push(1)
# Version 3: [1, 2]
s3 = s2.push(2)
# Version 4: [1, 2, 3]
s4 = s3.push(3)
# All versions still accessible!
print(f"s1: {s1.to_list()}") # []
print(f"s2: {s2.to_list()}") # [1]
print(f"s3: {s3.to_list()}") # [1, 2]
print(f"s4: {s4.to_list()}") # [1, 2, 3]
# Can branch from any version
s5 = s2.push(10) # Branch from s2
print(f"s5: {s5.to_list()}") # [1, 10]
10.2 Concurrent Stacks
import threading
from threading import Lock, Semaphore
from queue import Queue
class LockFreeStack:
"""
Lock-free stack using Compare-And-Swap (CAS)
Provides better scalability for concurrent access
"""
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def __init__(self):
self.top = None
self._lock = Lock() # Simulating CAS
def push(self, value):
"""Lock-free push"""
while True:
old_top = self.top
new_node = self.Node(value, old_top)
# Atomic compare-and-swap
if self._compare_and_swap(old_top, new_node):
return
# Retry if CAS failed
def pop(self):
"""Lock-free pop"""
while True:
old_top = self.top
if old_top is None:
raise IndexError("Stack is empty")
new_top = old_top.next
# Atomic compare-and-swap
if self._compare_and_swap(old_top, new_top):
return old_top.value
# Retry if CAS failed
def _compare_and_swap(self, expected, new_value):
"""
Atomic CAS operation (simulated with lock)
Real implementation would use atomic instructions
"""
with self._lock:
if self.top == expected:
self.top = new_value
return True
return False
class WorkStealingStack:
"""
Stack with work stealing for parallel processing
Used in parallel algorithms and thread pools
"""
def __init__(self):
self.local_stack = []
self.lock = Lock()
def push_local(self, item):
"""Push to local stack (no lock needed)"""
self.local_stack.append(item)
def pop_local(self):
"""Pop from local stack (no lock needed)"""
if self.local_stack:
return self.local_stack.pop()
return None
def steal(self):
"""Steal work from bottom of stack (needs lock)"""
with self.lock:
if self.local_stack:
return self.local_stack.pop(0) # Steal from bottom
return None
10.3 Specialized Stack Variants
Bounded Stack with Policies:
class BoundedStackWithPolicy:
"""
Stack with capacity limit and overflow policy
Policies:
- reject: Raise exception on overflow
- drop_oldest: Remove oldest (bottom) element
- drop_newest: Reject new element
"""
def __init__(self, capacity, policy='reject'):
self.capacity = capacity
self.policy = policy
self.items = []
def push(self, item):
"""Push with overflow handling"""
if len(self.items) >= self.capacity:
if self.policy == 'reject':
raise OverflowError("Stack is full")
elif self.policy == 'drop_oldest':
self.items.pop(0) # Remove oldest
self.items.append(item)
elif self.policy == 'drop_newest':
pass # Reject new item
else:
self.items.append(item)
def pop(self):
if not self.items:
raise IndexError("Stack is empty")
return self.items.pop()
**Max Stack:**
```python
class MaxStack:
"""
Stack with O(1) getMax operation
Similar to MinStack but tracks maximum
"""
def __init__(self):
self.stack = []
self.max_stack = []
def push(self, val):
self.stack.append(val)
if not self.max_stack:
self.max_stack.append(val)
else:
self.max_stack.append(max(val, self.max_stack[-1]))
def pop(self):
if not self.stack:
raise IndexError("Stack is empty")
self.max_stack.pop()
return self.stack.pop()
def top(self):
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1]
def getMax(self):
"""O(1) get maximum"""
if not self.max_stack:
raise IndexError("Stack is empty")
return self.max_stack[-1]
def popMax(self):
"""Remove and return maximum element"""
if not self.stack:
raise IndexError("Stack is empty")
max_val = self.max_stack[-1]
temp = []
# Pop until we find max
while self.stack[-1] != max_val:
temp.append(self.pop())
# Remove max
self.pop()
# Push back other elements
while temp:
self.push(temp.pop())
return max_val
10.4 Stack-Based Algorithms
Iterative DFS with State:
def iterative_dfs_with_state(graph, start):
"""
DFS with explicit state tracking
More control than recursive DFS
"""
stack = [(start, 'initial')] # (node, state)
visited = set()
result = []
while stack:
node, state = stack.pop()
if state == 'initial':
if node in visited:
continue
visited.add(node)
result.append(node)
# Push post-processing state
stack.append((node, 'post'))
# Push children (reversed for correct order)
for child in reversed(graph.get(node, [])):
stack.append((child, 'initial'))
elif state == 'post':
# Post-processing after all children visited
print(f"Finished processing {node}")
return result
def topological_sort_stack(graph):
"""
Topological sort using stack
Used in dependency resolution, task scheduling
"""
visited = set()
stack = []
def dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in graph.get(node, []):
dfs(neighbor)
stack.append(node) # Add after all dependencies
for node in graph:
dfs(node)
return stack[::-1] # Reverse for topological order
Stack-Based Parsing:
class StackBasedParser:
"""
Recursive descent parser using stack
Parse context-free grammars
"""
def __init__(self, grammar):
self.grammar = grammar
self.stack = []
def parse(self, input_string):
"""
Parse input according to grammar
Grammar: { 'S': ['A B', 'a'], 'A': ['a'], 'B': ['b'] }
"""
self.stack = [('S', input_string, 0)] # (symbol, input, position)
while self.stack:
symbol, input_str, pos = self.stack.pop()
if pos >= len(input_str):
if symbol == '': # Success
return True
continue
# Terminal symbol
if symbol.islower():
if input_str[pos] == symbol:
self.stack.append(('', input_str, pos + 1))
continue
# Non-terminal: try productions
for production in self.grammar.get(symbol, []):
# Push production symbols in reverse
new_stack_state = list(self.stack)
for prod_symbol in reversed(production.split()):
new_stack_state.append((prod_symbol, input_str, pos))
self.stack = new_stack_state
return False
10.5 Memory-Efficient Stack Techniques
Compressed Stack:
class CompressedStack:
"""
Stack that compresses consecutive duplicates
Useful for run-length encoding
"""
def __init__(self):
self.stack = [] # (value, count) pairs
def push(self, value):
"""Compress consecutive duplicates"""
if self.stack and self.stack[-1][0] == value:
# Increment count
val, count = self.stack.pop()
self.stack.append((val, count + 1))
else:
self.stack.append((value, 1))
def pop(self):
"""Pop and decompress"""
if not self.stack:
raise IndexError("Stack is empty")
val, count = self.stack[-1]
if count > 1:
self.stack[-1] = (val, count - 1)
else:
self.stack.pop()
return val
def size(self):
"""Total number of elements"""
return sum(count for val, count in self.stack)
# Example: [1,1,1,2,2,3] stored as [(1,3), (2,2), (3,1)]
Lazy Stack:
class LazyStack:
"""
Stack that defers operations until needed
Useful for optimization in complex algorithms
"""
def __init__(self):
self.stack = []
self.pending_ops = []
def push(self, value):
"""Immediate push"""
self._flush_pending()
self.stack.append(value)
def lazy_push_multiple(self, values):
"""Defer multiple pushes"""
self.pending_ops.append(('push_multiple', values))
def pop(self):
"""Flush pending and pop"""
self._flush_pending()
if not self.stack:
raise IndexError("Stack is empty")
return self.stack.pop()
def _flush_pending(self):
"""Execute all pending operations"""
while self.pending_ops:
op, data = self.pending_ops.pop(0)
if op == 'push_multiple':
self.stack.extend(data)
11. Meta-Learning Questions
11.1 When to Use Stack
Decision Framework:
def should_use_stack_decision_tree():
"""
Decision tree for stack usage
"""
decision_tree = {
"Question 1: Do you need LIFO ordering?": {
"Yes": "Continue to Q2",
"No": {
"FIFO needed": "Use Queue",
"Random access needed": "Use Array/List",
"Priority ordering": "Use Heap"
}
},
"Question 2: Are you processing nested structures?": {
"Yes": "Stack is excellent choice",
"Examples": [
"Balanced parentheses",
"HTML/XML parsing",
"Directory traversal"
]
},
"Question 3: Do you need to backtrack?": {
"Yes": "Stack is natural fit",
"Examples": [
"Maze solving",
"Puzzle solving",
"Game state management"
]
},
"Question 4: Are you implementing DFS?": {
"Yes": "Stack (explicit or call stack)",
"No": {
"BFS": "Use Queue",
"Best-first": "Use Priority Queue"
}
},
"Question 5: Do you need to reverse data?": {
"Yes": "Stack naturally reverses",
"Example": "Reverse string, reverse list"
}
}
return decision_tree
11.2 Pattern Recognition
def recognize_stack_patterns():
"""
Learn to recognize when stack is the solution
"""
patterns = {
"Keywords in Problem": {
"LIFO": "Direct indication",
"Most recent": "Stack tracks recency",
"Nested": "Stack handles nesting",
"Matching": "Pairs/brackets",
"Previous/Next greater/smaller": "Monotonic stack",
"Undo/Redo": "Two stacks",
"Backtrack": "State stack"
},
"Problem Characteristics": {
"Need to match pairs": {
"examples": ["Parentheses", "HTML tags"],
"solution": "Stack for opening elements"
},
"Process in reverse": {
"examples": ["Reverse string", "Postfix evaluation"],
"solution": "Stack naturally reverses"
},
"Track history": {
"examples": ["Browser history", "Undo"],
"solution": "Stack stores states"
},
"Precedence matters": {
"examples": ["Expression evaluation", "Operator precedence"],
"solution": "Stack handles precedence"
},
"Depth-first exploration": {
"examples": ["Tree traversal", "Graph DFS"],
"solution": "Stack for traversal"
}
}
}
return patterns
def problem_to_stack_mapping():
"""
Map common problem types to stack solutions
"""
mapping = {
"If problem asks for": {
"Valid parentheses/brackets": "Matching stack",
"Next greater/smaller element": "Monotonic stack",
"Evaluate expression": "Expression stack",
"Implement undo": "State stack",
"Tree/graph DFS": "Traversal stack",
"Simplify path": "Directory stack",
"Remove duplicates": "Stack-based filtering",
"Decode string": "Nested processing stack"
},
"If you see these constraints": {
"Process most recent first": "Stack",
"LIFO order required": "Stack",
"Nested structure": "Stack",
"Need O(1) operations": "Stack (maybe with auxiliary)",
"Reverse without extra space": "In-place stack"
}
}
return mapping
11.3 Learning from Mistakes
def common_mistakes_and_lessons():
"""
Learn from common mistakes
"""
mistakes = {
"Mistake 1": {
"error": "Using stack for random access",
"example": "Accessing middle element frequently",
"lesson": "Stack is for top access only",
"solution": "Use array/list instead"
},
"Mistake 2": {
"error": "Not checking empty before pop",
"example": "stack.pop() without if check",
"lesson": "Always validate before pop/peek",
"solution": "if stack: stack.pop()"
},
"Mistake 3": {
"error": "Using wrong monotonic order",
"example": "Increasing stack for next greater",
"lesson": "Decreasing stack for next greater",
"solution": "Match stack order to problem requirement"
},
"Mistake 4": {
"error": "Forgetting to handle duplicates",
"example": "Monotonic stack with equal elements",
"lesson": "Decide <= vs < in while condition",
"solution": "Test with duplicate values"
},
"Mistake 5": {
"error": "Not considering space for recursion",
"example": "Deep recursion without iteration alternative",
"lesson": "Recursion uses implicit stack",
"solution": "Use explicit stack for deep recursion"
},
"Mistake 6": {
"error": "Wrong operator precedence",
"example": "Evaluating 2+3*4 as (2+3)*4",
"lesson": "Must handle precedence correctly",
"solution": "Use precedence table"
}
}
return mistakes
def debugging_checklist():
"""
Checklist for debugging stack problems
"""
checklist = [
"✓ Check for empty stack before pop/peek",
"✓ Verify LIFO order is maintained",
"✓ Test with single element",
"✓ Test with empty stack",
"✓ Test with duplicates",
"✓ Check all brackets are matched",
"✓ Verify operator precedence is correct",
"✓ Test with maximum capacity (if bounded)",
"✓ Check for off-by-one errors in indices",
"✓ Verify no infinite loops in while conditions",
"✓ Test monotonic stack with equal elements",
"✓ Check recursion depth for large inputs"
]
return checklist
11.4 Problem-Solving Strategy
def stack_problem_solving_strategy():
"""
Systematic approach to stack problems
"""
strategy = {
"Step 1: Understand": {
"questions": [
"What needs to be tracked?",
"Is LIFO ordering natural?",
"Are there nested structures?",
"Do I need to match pairs?",
"Is this a known pattern?"
]
},
"Step 2: Choose Stack Type": {
"options": {
"Basic stack": "For simple LIFO operations",
"Monotonic stack": "For next greater/smaller",
"Two stacks": "For min/max tracking or queue",
"Stack + hash": "For O(1) lookup with stack"
}
},
"Step 3: Design Solution": {
"template": """
1. Initialize stack
2. Iterate through input
3. Decide push/pop conditions
4. Process popped elements
5. Handle remaining stack elements
"""
},
"Step 4: Handle Edge Cases": {
"consider": [
"Empty stack",
"Single element",
"All same elements",
"Duplicates",
"Maximum/minimum values"
]
},
"Step 5: Optimize": {
"techniques": [
"Use indices instead of values",
"Combine operations",
"Early termination",
"Space-time tradeoffs"
]
}
}
return strategy
def interview_preparation_roadmap():
"""
Structured learning path for stacks
"""
roadmap = {
"Week 1: Fundamentals": [
"Implement stack from scratch",
"Basic operations (push, pop, peek)",
"Balanced parentheses",
"Reverse string using stack"
],
"Week 2: Expression Evaluation": [
"Postfix evaluation",
"Infix to postfix conversion",
"Basic calculator",
"Calculator with precedence"
],
"Week 3: Monotonic Stack": [
"Next greater element",
"Next smaller element",
"Stock span problem",
"Daily temperatures"
],
"Week 4: Advanced Problems": [
"Largest rectangle in histogram",
"Trapping rain water",
"Min stack / Max stack",
"LRU Cache (with stack understanding)"
],
"Week 5: Backtracking": [
"Generate parentheses",
"N-Queens with stack",
"Maze solving",
"Subset generation"
],
"Week 6: Practice & Review": [
"Mixed problem sets",
"Timed practice",
"Mock interviews",
"Review common mistakes"
]
}
essential_problems = [
"Valid Parentheses",
"Min Stack",
"Evaluate Reverse Polish Notation",
"Next Greater Element",
"Largest Rectangle in Histogram",
"Basic Calculator II",
"Implement Queue using Stacks",
"Daily Temperatures",
"Decode String",
"Backspace String Compare"
]
return roadmap, essential_problems
11.5 Connecting Stack Concepts
def connect_stack_concepts():
"""
How different stack concepts relate
"""
connections = {
"Stack ↔ Recursion": {
"relationship": "Recursion uses implicit call stack",
"conversion": "Any recursion can be iterative with stack",
"example": "Tree traversal"
},
"Stack ↔ Queue": {
"relationship": "Dual structures (LIFO vs FIFO)",
"implementation": "Can implement each using the other",
"example": "Queue using two stacks"
},
"Stack ↔ DFS": {
"relationship": "DFS naturally uses stack",
"contrast": "BFS uses queue",
"insight": "Stack gives depth-first exploration"
},
"Basic Stack ↔ Min Stack": {
"relationship": "Augmented with auxiliary stack",
"pattern": "Additional stack tracks metadata",
"generalization": "Can track any aggregate (max, sum, etc.)"
},
"Stack ↔ Monotonic Stack": {
"relationship": "Constrained stack with ordering",
"use_case": "Optimize range queries",
"insight": "Constraint enables O(n) algorithms"
},
"Expression Parsing ↔ Tree Building": {
"relationship": "Stack builds expression tree",
"operators": "Internal nodes",
"operands": "Leaf nodes"
}
}
return connections
def synthesis_questions():
"""
Questions to deepen understanding
"""
questions = {
"Understanding": [
"Why is stack LIFO instead of FIFO?",
"What makes stack suitable for recursion simulation?",
"How does stack enable O(n) next greater element?",
"Why do we need two stacks for min stack?"
],
"Application": [
"When would you choose stack over array?",
"How would you implement undo/redo?",
"What stack variant solves this problem best?",
"Can this recursive solution become iterative?"
],
"Analysis": [
"What's the time complexity and why?",
"What causes the amortized O(1) behavior?",
"What are space complexity trade-offs?",
"How do edge cases affect performance?"
],
"Synthesis": [
"How can I combine stack with other structures?",
"What new problems can this pattern solve?",
"How does this relate to graph algorithms?",
"Can I generalize this solution?"
],
"Evaluation": [
"Is stack the best choice here?",
"What are alternatives and trade-offs?",
"How does this compare to recursive solution?",
"What optimizations are possible?"
]
}
return questions
Read Next
Start reading to get personalized recommendations
Explore Unread
Great job! You've read all available articles