stack.md

Stack Pattern

Overview

The stack pattern is one of the most fundamental and widely used patterns in computer science. It follows the Last In, First Out (LIFO) principle, making it perfect for problems involving nested structures, expression evaluation, and backtracking.

When to Use Stack Pattern

1. Expression Evaluation

• Reverse Polish Notation (RPN) evaluation
• Infix to Postfix conversion
• Parentheses matching and validation
• Calculator implementations

2. Nested Structure Processing

• Parentheses matching (valid parentheses, nested brackets)
• HTML/XML tag matching
• Function call tracking
• Nested object processing

3. Backtracking and Undo Operations

• Browser history (back button functionality)
• Text editor undo/redo
• Game state management
• Recursive algorithm simulation
• Generate Parentheses (iterative approach)

4. Monotonic Stack Problems

• Next greater element problems
• Largest rectangle in histogram
• Stock span problems
• Temperature problems

📊 Visual Guide

Monotonic Stack (Next Greater Element)

Maintains a decreasing sequence to find the next larger element.

graph TD
A[Start: Iterate nums] --> B{Stack Empty?}
B -- Yes --> C[Push Current Index]
B -- No --> D{nums[Top] < Current?}
D -- No (Keep Order) --> C
D -- Yes (Found Next Greater) --> E[Pop Top]
E --> F[Record Answer for Top]
F --> B

Loading

⚖️ Stack Variations Comparison

Stack Type	Invariant Property	Primary Use Case	Example
Standard LIFO	None	Nested structures, Undo/Redo	Valid Parentheses
Monotonic Increasing	Elements increase bottom-to-top	Next Smaller Element	Largest Rectangle Area
Monotonic Decreasing	Elements decrease bottom-to-top	Next Greater Element	Daily Temperatures
Min/Max Stack	Auxiliary stack tracks min/max	O(1) Min/Max Retrieval	Min Stack

Core Stack Operations

#include<stack>
#include<iostream>usingnamespacestd;voiddemonstrateStackOperations() {
stack<int> st;
// Push elements
st.push(1);
st.push(2);
st.push(3);
// Check if empty
cout << "Is empty: " << st.empty() << endl; // 0 (false)// Get size
cout << "Size: " << st.size() << endl; // 3// Access top element
cout << "Top element: " << st.top() << endl; // 3// Pop element
st.pop();
cout << "After pop, top: " << st.top() << endl; // 2// Pop all elementswhile (!st.empty()) {
cout << "Popping: " << st.top() << endl;
st.pop();
}
}

Pattern 1: Expression Evaluation

Reverse Polish Notation (RPN)

classSolution {
public:intevalRPN(vector<string>& tokens) {
stack<int> st;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (token == "+") st.push(a + b);
elseif (token == "-") st.push(a - b);
elseif (token == "*") st.push(a * b);
elseif (token == "/") st.push(a / b);
} else {
st.push(stoi(token));
}
}
return st.top();
}
};

Key Insights for RPN

• Operand order matters: Second popped operand is the right operand
• Stack naturally handles the LIFO nature of operations
• Division truncates toward zero as required

Pattern 2: Parentheses Matching

Valid Parentheses

classSolution {
public:boolisValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
if (st.empty()) returnfalse;
char top = st.top();
st.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
returnfalse;
}
}
}
return st.empty();
}
};

Key Insights for Parentheses

• Opening brackets go on stack
• Closing brackets must match the most recent opening bracket
• Stack empty check is crucial for valid sequences

Pattern 3: Monotonic Stack

Next Greater Element

classSolution {
public:
vector<int> nextGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st; // Store indicesfor (int i = 0; i < n; i++) {
while (!st.empty() && nums[st.top()] < nums[i]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
}
};

Key Insights for Monotonic Stack

• Maintain decreasing order in stack
• Process elements that are smaller than current
• Store indices for result mapping

Pattern 4: Nested Structure Processing

Simplify Path

classSolution {
public:
string simplifyPath(string path) {
stack<string> st;
stringstream ss(path);
string token;
while (getline(ss, token, '/')) {
if (token == "" || token == ".") continue;
if (token == "..") {
if (!st.empty()) st.pop();
} else {
st.push(token);
}
}
if (st.empty()) return"/";
string result = "";
while (!st.empty()) {
result = "/" + st.top() + result;
st.pop();
}
return result;
}
};

Common Stack Patterns

1. Two-Stack Approach

// Min Stack implementationclassMinStack {
private:
stack<int> data;
stack<int> minStack;
public:voidpush(int val) {
data.push(val);
if (minStack.empty() || val <= minStack.top()) {
minStack.push(val);
}
}
voidpop() {
if (data.top() == minStack.top()) {
minStack.pop();
}
data.pop();
}
inttop() { return data.top(); }
intgetMin() { return minStack.top(); }
};

2. Stack with Additional Data

// Stack with getMax() in O(1)classMaxStack {
private:
stack<int> data;
stack<int> maxStack;
public:voidpush(int val) {
data.push(val);
if (maxStack.empty() || val >= maxStack.top()) {
maxStack.push(val);
}
}
voidpop() {
if (data.top() == maxStack.top()) {
maxStack.pop();
}
data.pop();
}
inttop() { return data.top(); }
intgetMax() { return maxStack.top(); }
};

Advanced Stack Applications

1. Largest Rectangle in Histogram

classSolution {
public:intlargestRectangleArea(vector<int>& heights) {
stack<int> st;
int maxArea = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!st.empty() && heights[st.top()] > h) {
int height = heights[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = max(maxArea, height * width);
}
st.push(i);
}
return maxArea;
}
};

2. Generate Parentheses (Iterative Approach)

classSolution {
public:
vector<string> generateParenthesis(int n) {
vector<string> results;
stack<tuple<string, int, int>> st;
// Push initial state: (current_string, open_count, close_count)
st.push(make_tuple("", 0, 0));
while (!st.empty()) {
auto [current, open, close] = st.top();
st.pop();
// Base case: we've generated a complete valid combinationif (open == close && close == n) {
results.push_back(current);
continue;
}
// Add opening parenthesis if we haven't used all nif (open < n) {
st.push(make_tuple(current + "(", open + 1, close));
}
// Add closing parenthesis if we have more '(' than ')'if (close < open) {
st.push(make_tuple(current + ")", open, close + 1));
}
}
return results;
}
};

3. Trapping Rain Water

classSolution {
public:inttrap(vector<int>& height) {
stack<int> st;
int water = 0;
for (int i = 0; i < height.size(); i++) {
while (!st.empty() && height[st.top()] < height[i]) {
int top = st.top();
st.pop();
if (st.empty()) break;
int distance = i - st.top() - 1;
int boundedHeight = min(height[i], height[st.top()]) - height[top];
water += distance * boundedHeight;
}
st.push(i);
}
return water;
}
};

Stack vs Other Data Structures

Problem Type	Best Data Structure	Reason
Expression Evaluation	Stack	Natural LIFO for operations
Parentheses Matching	Stack	Nested structure processing
Next Greater Element	Monotonic Stack	Maintain order efficiently
BFS Traversal	Queue	FIFO for level-order
DFS Traversal	Stack/Recursion	LIFO for depth-first

Common Pitfalls

1. Stack Underflow

// Always check if stack is empty before poppingif (!st.empty()) {
int top = st.top();
st.pop();
}

2. Wrong Operand Order

// In RPN: second popped is right operandint b = st.top(); st.pop(); // Right operandint a = st.top(); st.pop(); // Left operandint result = a + b; // Correct order

3. Forgetting to Handle Edge Cases

// Check for empty stack in final resultreturn st.empty() ? 0 : st.top();

Practice Problems

Easy

• 20. Valid Parentheses
• 155. Min Stack
• 225. Implement Stack using Queues

Medium

• 150. Evaluate Reverse Polish Notation
• 71. Simplify Path
• 739. Daily Temperatures

Hard

• 84. Largest Rectangle in Histogram
• 42. Trapping Rain Water
• 85. Maximal Rectangle

Key Takeaways

1. Stack is perfect for nested structures and expression evaluation
2. LIFO principle naturally handles many algorithmic problems
3. Monotonic stacks are powerful for range queries
4. Always check for empty stack before operations
5. Operand order matters in expression evaluation
6. Stack can simulate recursion for iterative solutions

Related Patterns

• Queue Pattern - FIFO operations
• Two Pointers - Alternative to stack for some problems
• Sliding Window - Often combined with stack
• Tree Traversal - Stack-based iterative DFS