The Stack of Plates Analogy
Picture a stack of plates in a cafeteria:
- Add a plate: Put it on TOP
- Remove a plate: Take from TOP
- Can't access middle plates without removing the ones above!
Stacks work exactly like this.
The last item you add is the first one you remove. This is called LIFO: Last In, First Out.
Stack Operations
The Core Four
PUSH - Add item to top
Stack: [A, B]
push(C)
Stack: [A, B, C] ← C is now on top
POP - Remove and return top item
Stack: [A, B, C]
pop() → returns C
Stack: [A, B] ← C is gone
PEEK/TOP - Look at top item (without removing)
Stack: [A, B, C]
peek() → returns C
Stack: [A, B, C] ← C still there
IS_EMPTY - Check if stack has items
Stack: []
isEmpty() → true
All O(1) Operations!
Every stack operation is constant time - no matter how many items are in the stack.
Visual Walkthrough
Starting empty:
| | |
| _____ | ← bottom |
push(1):
| 1 |
| _____ |
push(2):
| 2 |
| 1 |
| _____ |
push(3):
| 3 | ← top (most recent) |
| 2 | |
| 1 | |
| _____ | |
pop() → 3:
| 2 | ← new top |
| 1 | |
| _____ | |
peek() → 2 (stack unchanged)
Where Stacks Are Used
1. The Call Stack (Function Calls)
Every time you call a function, it's "pushed" onto the call stack:
main() calls → foo() calls → bar()
Call Stack:
| bar() | ← currently executing |
| foo() | |
| main() | |
| _________ | |
bar() returns → popped
foo() resumes
foo() returns → popped
main() resumes
Stack overflow happens when too many functions are nested (stack gets too deep).
2. Undo/Redo
User types "Hello"
Undo stack: [type "Hello"]
User deletes "o"
Undo stack: [type "Hello", delete "o"]
User clicks Undo
Pop: delete "o" → reverse it (re-add "o")
Undo stack: [type "Hello"]
3. Browser Back Button
Visit: Google → Facebook → Twitter
Back stack: [Google, Facebook, Twitter]
Click back:
Pop Twitter, go to Facebook
Back stack: [Google, Facebook]
4. Expression Evaluation
Parsing mathematical expressions uses stacks:
Expression: 3 + 4 * 2
Operator stack helps respect order of operations!
Classic Stack Problems
1. Valid Parentheses
Problem: Are brackets properly matched? "([{}])" ✓, "([)]" ✗
Input: "([{}])"
( → push Stack: [(]
[ → push Stack: [(, []
{ → push Stack: [(, [, {]
} → matches { → pop Stack: [(, []
] → matches [ → pop Stack: [(]
) → matches ( → pop Stack: []
Stack empty at end → Valid!
2. Next Greater Element
Problem: For each element, find the next larger element to its right.
Array: [4, 5, 2, 10]
Use stack to track elements waiting for their "next greater":
4 waits... 5 is greater! 4's answer = 5
5 waits... 2 is smaller, keep waiting
5 waits... 10 is greater! 5's answer = 10
2 waits... 10 is greater! 2's answer = 10
10 has nothing → -1
Result: [5, 10, 10, -1]
3. Min Stack
Problem: Stack that also tracks minimum in O(1).
Main stack: [5, 3, 7, 2]
Min stack: [5, 3, 3, 2] ← tracks min at each level
getMin() → peek min stack → 2
pop() → removes 2 from both
getMin() → now 3
4. Evaluate Reverse Polish Notation
Input: ["2", "1", "+", "3", "*"]
2 → push Stack: [2]
1 → push Stack: [2, 1]
+ → pop 1,2, push 2+1=3 Stack: [3]
3 → push Stack: [3, 3]
* → pop 3,3, push 3*3=9 Stack: [9]
Result: 9
Stack vs Queue
| Property | Stack | Queue |
|---|---|---|
| Order | LIFO (Last In First Out) | FIFO (First In First Out) |
| Add | Top (push) | Back (enqueue) |
| Remove | Top (pop) | Front (dequeue) |
| Analogy | Stack of plates | Line at store |
| Use | Undo, recursion, parsing | Scheduling, BFS |
Implementation Options
Array-Based
Stack using array:
[A, B, C, _, _, _]
↑ top_index = 2
push(D): arr[3] = D, top_index = 3
pop(): return arr[2], top_index = 1
Pros: Simple, cache-friendly Cons: May need resizing
Linked List-Based
Stack using linked list:
top → [C] → [B] → [A] → null
push(D): new node [D] → [C] → ...
pop(): return top, top = top.next
Pros: No size limit, no resizing Cons: More memory per element
Common Mistakes
1. Popping from Empty Stack
Usually check isEmpty() (or handle an empty case) before pop() or peek().
2. Not Considering Stack Overflow
Recursive algorithms can exceed stack depth. Python default is ~1000 calls.
3. Using Queue When Stack Needed
FIFO vs LIFO matters! Wrong choice gives wrong results.
FAQ
Q: When should I use a stack?
When you need to process items in reverse order of arrival - undo, backtracking, matching pairs.
Q: Is array or linked list better for stack?
Arrays are often a good default (simple, cache-friendly). Use a linked list when you need growth without resizing or you want O(1) push/pop without a fixed capacity.
Q: How is stack related to recursion?
Each recursive call is pushed onto the call stack. Recursion IS using a stack implicitly!
Q: What's the difference between stack and heap memory?
Stack memory: automatic, for function calls (the call stack). Heap memory: manual, for dynamic allocation. Different concept despite similar name!
Summary
A stack is a LIFO data structure - last in, first out.
Key Takeaways:
- Push, pop, peek - all O(1)
- LIFO: Last In, First Out
- Used in: function calls, undo, parsing, backtracking
- Check empty before pop/peek
- Array or linked list implementation
- Foundation for many algorithms
Stacks are everywhere in programming - from function calls to expression parsing!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.