Day 10: Stack Data Structure | LIFO Principles & Python Implementation
Master LIFO principles, push/pop operations, and how Undo buttons work under the hood.
Day 10: Stack Data Structure Explained Simply
Why is the strict rule "last one in, first one out" the secret behind your code editor's Undo button and your browser's crash recovery?
In 30 Seconds
A Stack is a linear data structure that enforces one strict rule: LIFO (**Last-In, First-Out** [the newest item added is always the very first item removed]). You can only add items to the very top (push) and remove items from the very top (pop). You are never allowed to pull an item out from the middle or the bottom. This deliberate restriction makes stacks blazingly fast ($O(1)$ for every operation) and ideal for tracking nested tasks.
The Real-World Analogy: A Spring-Loaded Cafeteria Plate Dispenser
Picture the stainless-steel plate warmer at an all-you-can-eat buffet.
- A kitchen worker washes five clean plates and pushes them down onto the spring-loaded cylinder one after another: Plate 1 goes in first, followed by 2, 3, 4, and finally Plate 5 sitting right on top.
- When a hungry customer walks up, they grab Plate 5 off the top—never Plate 1 from the bottom.
- The last plate placed onto the stack is always the first plate taken off.
Picture This
Here is a visual diagram showing how push and pop modify a LIFO Stack from the top end only:
PUSH(30) TOP -> [ 30 ] <-- Added last, removed first!
| [ 20 ]
v [ 10 ]
+------+ +------+
| 20 | ---> POP() returns 30, leaving [20] as the new TOP.
| 10 |
+------+
And here is how a Stack checks balanced brackets in code ("{[()]}"):
Input: { [ ( ) ] }
| | | | | |
Stack: { [ ( | | |
^---+ | | <-- ')' matches top '(', pop '('!
^-----------+ | <-- ']' matches top '[', pop '['!
^-------------------+ <-- '}' matches top '{', pop '{'!
End result: Stack is empty -> Valid syntax!
How It Actually Works
- Pick a Backing Store: Build a stack using a dynamic array (Python
list) or a singly linked list whereheadacts as the top. - Push to the Top ($O(1)$): Append the new item to the end of the array and update your
toptracker. - Peek Before You Leap ($O(1)$): Read the top item without removing it so you can inspect what's next safely.
- Pop from the Top ($O(1)$): Remove and return the most recently added item, raising an underflow error if empty.
Show Me The Code
# Day 10: Stack Data Structure Implemented from Scratch in Python
class Stack:
def __init__(self):
self._items = []
def push(self, item):
"""Places an item onto the top of the stack in O(1) amortized time."""
self._items.append(item)
def pop(self):
"""Removes and returns the top item in O(1) time."""
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack.")
return self._items.pop()
def peek(self):
"""Looks at the top item without removing it in O(1) time."""
if self.is_empty():
return None
return self._items[-1]
def is_empty(self):
return len(self._items) == 0
if __name__ == "__main__":
undo_history = Stack()
undo_history.push("Typed 'Hello'")
undo_history.push("Bolded 'Hello'")
undo_history.push("Deleted 'o'")
print("Top action right now:", undo_history.peek()) # Output: Deleted 'o'
print("Undoing:", undo_history.pop()) # Output: Deleted 'o'
print("Now at top:", undo_history.peek()) # Output: Bolded 'Hello'
Dry Run
| Step | Operation | Stack State (Bottom -> Top) | Return Value |
|---|---|---|---|
| 1 | push(5) | [5] | None |
| 2 | push(12) | [5, 12] | None |
| 3 | peek() | [5, 12] | 12 |
| 4 | pop() | [5] | 12 |
Speed & Memory
| Operation | Best Case | Average Case | Worst Case | Why? |
|---|---|---|---|---|
| Push | $O(1)$ | $O(1)$ | $O(1)$* | Appends straight to the top (*amortized for dynamic arrays). |
| Pop | $O(1)$ | $O(1)$ | $O(1)$ | Removes the last element with zero shifting. |
| Peek | $O(1)$ | $O(1)$ | $O(1)$ | Direct lookup of the top slot. |
Where You'll See It In Real Life
- Undo / Redo in Editors: Pressing
Ctrl+Zpops the latest edit off your action stack. - Compiler Bracket Checking: Code editors verify that every opening bracket has a matching closing partner in exact reverse order.
- Program Call Stack: Programming languages track active function calls and local variables using an execution stack.
Traps To Avoid
- Trap 1: Calling
pop()without checkingis_empty().
Fix: Always verify the stack isn't empty to avoid runtime underflow errors. - Trap 2: Using
insert(0, item)andpop(0)on a Python list.
Fix: Push and pop from the end (append/pop) so operations run in $O(1)$ instead of $O(N)$. - Trap 3: Accessing middle elements by index.
Fix: Respect LIFO boundaries; use an array if you need random middle access.
Practice
- Easy: Write a function
reverse_string(text)that uses a Stack to reverse a word. - Medium: Write
is_valid_brackets(s)to verify balanced parentheses, brackets, and curly braces. - Hard: Design a
MinStackclass supportingpush,pop,top, andget_minall in $O(1)$ time. (Hint: Use a second stack tracking the running minimum!)
TL;DR
- A Stack follows LIFO (**Last-In, First-Out**): the newest item added is always removed first.
push,pop, andpeekall run in $O(1)$ constant time.- Stacks power Undo features, bracket validators, and function call management.
References Consulted
- GeeksforGeeks - Stack Data Structure — referenced for verification — all content above is original.
- Programiz - Stack Data Structure and Implementation — referenced for verification — all content above is original.
Covered Log Update
Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List, Doubly Linked List, Stack]