🥞 Stacks: Your Secret Weapon for Organizing Data
Imagine a stack of pancakes. You can only eat from the top. You can only add to the top. That’s exactly how a Stack works in programming!
🎯 What You’ll Master
- Stack Fundamentals
- Balanced Parentheses
- Simplify Path
- Longest Valid Parentheses
- Remove Invalid Parentheses
- Minimum Add to Make Valid
📚 Stack Fundamentals
The Pancake Rule: Last In, First Out (LIFO)
Think about a stack of plates at a buffet. When someone washes a plate, they put it on top. When you need a plate, you take from the top. The last plate added is the first one taken!
# Creating a stack in Python
stack = []
# Push: Add to the top
stack.append("plate1")
stack.append("plate2")
stack.append("plate3")
# Pop: Remove from top
top_plate = stack.pop()
# top_plate = "plate3"
The Three Magic Moves
| Operation | What It Does | Python Code |
|---|---|---|
| Push | Add item to top | stack.append(x) |
| Pop | Remove & return top | stack.pop() |
| Peek | Look at top (no remove) | stack[-1] |
When Is the Stack Empty?
# Check if empty
if len(stack) == 0:
print("Stack is empty!")
# Or simply:
if not stack:
print("Nothing here!")
🔐 Balanced Parentheses
The Matching Game
Imagine you’re checking if every door that opens also closes. Every ( needs a ). Every { needs a }. Every [ needs a ].
Valid Examples:
()✅()[]{}✅{[()]}✅
Invalid Examples:
(]❌ (wrong match)([)]❌ (crossed wires){❌ (never closed)
The Secret Trick
When you see an opening bracket, push it onto the stack. When you see a closing bracket, pop from the stack and check if they match!
def is_balanced(s):
stack = []
matches = {')':'(', '}':'{', ']':'['}
for char in s:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack:
return False
if stack.pop() != matches[char]:
return False
return len(stack) == 0
Visual Flow
graph TD A["Input: {[#40;#41;]}"] --> B["See { → Push"] B --> C["See [ → Push"] C --> D["See #40; → Push"] D --> E["See #41; → Pop, Match!"] E --> F["See ] → Pop, Match!"] F --> G["See } → Pop, Match!"] G --> H["Stack Empty → Valid!"]
🗂️ Simplify Path
The Folder Navigator
You’re navigating folders on a computer. The path /a/./b/../../c/ looks messy. Let’s clean it up!
Special Symbols:
.= Stay here (do nothing)..= Go back one folder (pop from stack)- Everything else = Enter that folder (push to stack)
Example Journey
Input: "/a/./b/../../c/"
Step 1: "a" → Push → Stack: [a]
Step 2: "." → Stay → Stack: [a]
Step 3: "b" → Push → Stack: [a, b]
Step 4: ".." → Pop → Stack: [a]
Step 5: ".." → Pop → Stack: []
Step 6: "c" → Push → Stack: [c]
Output: "/c"
The Code
def simplify_path(path):
stack = []
parts = path.split('/')
for part in parts:
if part == '..':
if stack:
stack.pop()
elif part and part != '.':
stack.append(part)
return '/' + '/'.join(stack)
🏆 Longest Valid Parentheses
The Longest Streak Challenge
Given a string of only ( and ), find the longest stretch that’s perfectly balanced.
Example:
- Input:
"(()"→ Answer:2(the()part) - Input:
")()())"→ Answer:4(the()()part)
The Smart Stack Trick
Instead of storing brackets, we store positions! This helps us calculate lengths.
def longest_valid(s):
stack = [-1] # Base marker
max_length = 0
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
length = i - stack[-1]
max_length = max(max_length, length)
return max_length
Walking Through )()())
graph TD A["i=0: #41; → Pop -1, Push 0"] --> B["Stack: [0]"] B --> C["i=1: #40; → Push 1"] C --> D["Stack: [0,1]"] D --> E["i=2: #41; → Pop 1"] E --> F["Length = 2-0 = 2"] F --> G["i=3: #40; → Push 3"] G --> H["i=4: #41; → Pop 3"] H --> I["Length = 4-0 = 4 🏆"]
🧹 Remove Invalid Parentheses
The Cleanup Crew
You have a messy string with letters and brackets. Remove the minimum number of brackets to make it valid. Find all possible valid results!
Example:
- Input:
"()())()" - Output:
["()()()", "(())()"]
The Two-Pass Strategy
- Left to Right: Remove extra
) - Right to Left: Remove extra
(
def remove_invalid(s):
def clean(s, open_br, close_br):
result = []
stack = []
for char in s:
if char == open_br:
stack.append(char)
elif char == close_br:
if stack:
stack.pop()
else:
continue # Skip invalid
result.append(char)
return ''.join(result)
# Pass 1: Remove extra )
temp = clean(s, '(', ')')
# Pass 2: Remove extra (
temp = clean(temp[::-1], ')', '(')
return temp[::-1]
Visual Cleanup
Input: "()())()"
Pass 1 (L→R): Remove extra )
"()())()" → "()()()"
Pass 2 (R→L): Check for extra (
Already clean! ✅
Output: "()()()"
➕ Minimum Add to Make Valid
The Repair Counter
How many brackets do you need to add to make the string valid?
Examples:
"())"→ Need 1(→ Answer:1"((("→ Need 3)→ Answer:3"()"→ Already valid → Answer:0
The Simple Counter Method
No stack needed! Just count unmatched brackets.
def min_add(s):
open_needed = 0 # Unmatched )
close_needed = 0 # Unmatched (
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
Example Walkthrough: "())"
graph TD A["Start: open=0, close=0"] --> B["#40; → close++ = 1"] B --> C["#41; → close-- = 0"] C --> D["#41; → close=0, so open++ = 1"] D --> E["Answer: 0 + 1 = 1"]
🎮 Quick Reference Card
| Problem | Key Insight | Time |
|---|---|---|
| Balanced Parentheses | Match closing with stack top | O(n) |
| Simplify Path | Push folders, pop on .. |
O(n) |
| Longest Valid | Store indices, not chars | O(n) |
| Remove Invalid | Two-pass cleanup | O(n) |
| Minimum Add | Count unmatched both ways | O(n) |
🌟 The Big Picture
graph TD A["🥞 STACK"] --> B["Push/Pop/Peek"] B --> C["Balanced Check"] B --> D["Path Simplify"] B --> E["Longest Valid"] B --> F["Remove Invalid"] B --> G["Minimum Add"] C --> H["Match Pairs"] D --> H E --> I["Track Positions"] F --> I G --> J["Count Unmatched"]
💡 Remember This!
Stacks are like a to-do list where you always do the most recent task first.
Every time you see matching pairs (brackets, tags, operations), think STACK!
You’ve now mastered the art of stacks. From balancing brackets to simplifying paths, you have the tools to tackle any stack-based problem with confidence! 🚀