Pure Python Stacks (LIFO) & Call Stack Mechanics
A stack is a Last-In, First-Out (LIFO) structure. Python lists implement stacks natively: `.append()` pushes in amortized $O(1)$, and `.pop()` removes from the top in $O(1)$ 🥞.
stack = []
# Push operations:
stack.append("view_profile")
stack.append("edit_settings")
# Pop operations (LIFO order):
print(stack.pop()) # 'edit_settings' (most recent first) 🥞
print(stack.pop()) # 'view_profile'
# 3. Pure Python Stacks (LIFO) & Call Stack Mechanics A stack is a Last-In, First-Out (LIFO) structure. Python lists implement stacks natively: `.append()` pushes in amortized $O(1)$, and `.pop()` removes from the top in $O(1)$ 🥞. ```python stack = [] # Push operations: stack.append("view_profile") stack.append("edit_settings") # Pop operations (LIFO order): print(stack.pop()) # 'edit_settings' (most recent first) 🥞 print(stack.pop()) # 'view_profile' ``` Browser back-buttons, undo/redo buffers, and compiler syntax parsers all rely on stacks to reverse history! 🥞 --- ### Question Why is `list.pop()` $O(1)$ while `list.pop(0)` is $O(n)$ in Python? 🧠- [ ] a. `pop()` removes from the end of the array; `pop(0)` forces every subsequent element to shift left in memory 🥞 - [ ] b. `pop(0)` triggers a full garbage collection cycle - [ ] c. Python automatically sorts the list after `pop(0)` - [ ] d. `pop()` is executed on GPU while `pop(0)` runs on CPU --- ### Challenge Create `stack = []`. Push `10, 20, 30`. Pop two elements and print their sum. 🎯 <details> <summary>Solution</summary> ```python stack = [] stack.append(10) stack.append(20) stack.append(30) val1 = stack.pop() val2 = stack.pop() print(val1 + val2) ``` </details>