Stacks
Master the Last In, First Out (LIFO) data structure
š What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Think of it like a stack of plates - you can only add or remove plates from the top!
# Simple stack implementation using Python list
stack = []
# Push elements (add to top)
stack.append(10) # [10]
stack.append(20) # [10, 20]
stack.append(30) # [10, 20, 30]
# Pop elements (remove from top)
top = stack.pop() # Returns 30, stack becomes [10, 20]
print(f"Popped: {top}")
print(f"Stack: {stack}")
LIFO
Order
O(1)
Operations
Top
Access
Stack Operations
Push
Add element to the top
O(1)
Insert
Pop
Remove element from the top
O(1)
Remove
Peek/Top
View top element without removing
O(1)
Read
isEmpty
Check if stack is empty
O(1)
Check
Stack Visualization
Understanding how elements are added and removed:
Stack Operations: Push and Pop
30 ā Top
20
10 ā Bottom
Push/Pop here
Middle
First element
Lesson 1: Simple Stack Implementation
Let's create a basic Stack class with essential operations:
Basic Stack Class
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""Add item to top"""
self.items.append(item)
def pop(self):
"""Remove and return top item"""
if self.is_empty():
return None
return self.items.pop()
def peek(self):
"""View top item without removing"""
if self.is_empty():
return None
return self.items[-1]
def is_empty(self):
"""Check if stack is empty"""
return len(self.items) == 0
def size(self):
"""Get number of items"""
return len(self.items)
# Simple example
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(f"Top: {stack.peek()}") # 30
print(f"Pop: {stack.pop()}") # 30
print(f"Size: {stack.size()}") # 2
Lesson 2: Real-World Applications
Stacks are used in many important applications:
Function Calls
- Call stack in programming
- Recursion management
- Return address storage
- Local variable storage
Expression Evaluation
- Parentheses matching
- Infix to postfix conversion
- Calculator operations
- Syntax parsing
Browser & Editor
- Browser back button
- Undo operations
- Text editor history
- Navigation history
Algorithms
- Depth-First Search (DFS)
- Backtracking algorithms
- Memory management
- Compiler design
Lesson 3: Balanced Parentheses Checker
Check if brackets are properly matched using a stack:
Simple Parentheses Checker
def is_balanced(text):
"""Check if parentheses are balanced"""
stack = []
pairs = {'(': ')', '[': ']', '{': '}'}
for char in text:
if char in pairs: # Opening bracket
stack.append(char)
elif char in pairs.values(): # Closing bracket
if not stack:
return False
if pairs[stack.pop()] != char:
return False
return len(stack) == 0
# Test examples
examples = ["()", "((()))", "([{}])", "(()", "([)]"]
for example in examples:
result = "ā" if is_balanced(example) else "ā"
print(f"{example} ā {result}")
# Output:
# () ā ā
# ((()) ā ā
# ([{}]) ā ā
# (() ā ā
# ([)] ā ā
Lesson 4: Simple Undo System
Create basic undo functionality using a stack:
Simple Text Editor
class SimpleEditor:
def __init__(self):
self.text = ""
self.history = [] # Stack for undo
def write(self, new_text):
"""Add text"""
self.history.append(self.text) # Save current state
self.text += new_text
print(f"Text: '{self.text}'")
def undo(self):
"""Undo last action"""
if self.history:
self.text = self.history.pop()
print(f"Undo ā Text: '{self.text}'")
else:
print("Nothing to undo!")
# Example usage
editor = SimpleEditor()
editor.write("Hello") # Text: 'Hello'
editor.write(" World") # Text: 'Hello World'
editor.write("!") # Text: 'Hello World!'
editor.undo() # Undo ā Text: 'Hello World'
editor.undo() # Undo ā Text: 'Hello'
editor.undo() # Undo ā Text: ''
Lesson 5: Calculator with Stack
Evaluate simple math expressions using a stack:
Postfix Calculator
def calculate_postfix(expression):
"""
Calculate postfix expression
Example: "3 4 +" means 3 + 4 = 7
"""
stack = []
tokens = expression.split()
for token in tokens:
if token in ['+', '-', '*', '/']:
# Pop two numbers
b = stack.pop()
a = stack.pop()
# Calculate result
if token == '+':
result = a + b
elif token == '-':
result = a - b
elif token == '*':
result = a * b
elif token == '/':
result = a / b
# Push result back
stack.append(result)
else:
# It's a number
stack.append(float(token))
return stack[0]
# Examples
examples = [
"3 4 +", # 3 + 4 = 7
"5 2 -", # 5 - 2 = 3
"6 2 /", # 6 / 2 = 3
"3 4 + 2 *" # (3 + 4) * 2 = 14
]
for expr in examples:
result = calculate_postfix(expr)
print(f"{expr} = {result}")
Practice Project: Browser Back Button
Simple browser history using a stack:
Browser History
class Browser:
def __init__(self):
self.current_page = "home.com"
self.history = [] # Stack for back button
def visit(self, page):
"""Visit a new page"""
self.history.append(self.current_page)
self.current_page = page
print(f"Visiting: {page}")
def back(self):
"""Go back to previous page"""
if self.history:
previous = self.history.pop()
print(f"Going back from {self.current_page} to {previous}")
self.current_page = previous
else:
print("No previous page!")
def current(self):
"""Show current page"""
print(f"Current page: {self.current_page}")
# Example usage
browser = Browser()
browser.visit("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.current() # Current page: github.com
browser.back() # Going back to youtube.com
browser.back() # Going back to google.com
browser.back() # Going back to home.com
browser.back() # No previous page!