Stacks Basics
""" STACKS - BASICS
-------------------
A stack is a collection of items with restricted access:
- You can only add items to the TOP
- You can only remove items from the TOP
This rule is called LIFO:
- Last In, First Out
It is like:
- A stack of plates
- Browser back history
- Undo/Redo in an editor
You can't remove the middle item or inspect everything freely.
Python does not have a special Stack type,
but lists already support stack behavior.
List methods:
- append() -> push to top (end)
- pop() -> remove from top (end)
Example: Undo user action
-------------------------
"""
# Stack to store user actions
undo_stack = []
# User performs actions
undo_stack.append("Type Hello")
undo_stack.append("Type World")
undo_stack.append("Delete World")
# Current actions stack
print("Current stack:", undo_stack) # ['Type Hello', 'Type World', 'Delete World']
# User presses Undo
last_action = undo_stack.pop()
print("Undo action:", last_action) # Undo action: Delete World
# Current actions stack
print("Current stack:", undo_stack) # ['Type Hello', 'Type World']
Custom Stack
""" CUSTOM STACK - TYPE
-----------------------
Most languages do not provide stacks, so we create our own.
This is good for enforcing rules and readability.
With a raw list, this is posible:
stack = [1, 2, 3]
stack.insert(0, 99) - breaks stack rules
stack[1] = 42 - breaks stack rules
With a Stack class:
stack.push(1)
stack.push(2)
stack.push(3) - no way to touch the middle
Example:
- Undo functionality
----------------------
"""
class Stack:
def __init__(self):
self.items = [] # Internal storage
def push(self, item):
self.items.append(item) # Add item to top of stack
def pop(self):
if not self.items:
return None
return self.items.pop() # Remove and return top item
def peek(self):
if not self.items:
return None
return self.items[-1] # Read top item without removing it
# Create stack
undo_stack = Stack()
# Add actions
undo_stack.push("Type: Hello")
undo_stack.push("Type: World")
undo_stack.push("Delete: World")
# Undo last action
undo_stack.pop()
# New top
print("Top:", undo_stack.peek())
print("Stack:", undo_stack.items)
# -------------------------------------
# Top: Type: World
# Stack: ['Type: Hello', 'Type: World']
Collections Deque
""" COLLECTIONS - DEQUE
-----------------------
Features:
- Similar performance as custom stack implementation.
- Better for queues
- Also used as stack sometimes
No custom class needed most of the time.
Example:
- Browser History Stack (deque)
--------------------------------
"""
from collections import deque
# Max number of pages to remember
MAX_HISTORY = 5
# Stack for browser history
history = deque(maxlen=MAX_HISTORY)
# User visits pages
history.append("google.com")
history.append("openai.com")
history.append("gitub.com")
history.append("python.org")
history.append("minte9.com")
print("History:", list(history))
# Visit one more page (oldest is removed automatically) - Look Here
history.append("stackoverflow.com")
print("History:", list(history))
# User click BACK
last_page = history.pop()
print("Back to:", last_page)
print("History:", list(history))
# ------------------------------
# History: ['google.com', 'openai.com', 'gitub.com', 'python.org', 'minte9.com']
# History: ['openai.com', 'gitub.com', 'python.org', 'minte9.com', 'stackoverflow.com']
# Back to: stackoverflow.com
# History: ['openai.com', 'gitub.com', 'python.org', 'minte9.com']
