Stack
A Stack is a linear data structure adhering to Last-In-First-Out (LIFO) access rules. Elements are pushed onto the top of the stack and popped off the top.
Why It Exists
Many systems require backtracking. Stacks store previous computational contexts, allowing processes to return to parent states on demand.
Intuition for Beginners
“Think of a stack of plates in a cafeteria. You place new plates on top (push). When a customer takes a plate, they remove it from the top (pop). You cannot extract the bottom plate without removing the ones above first.”
Visual Explanation
Stack Push/Pop Lifecycle:
| |
| [ 30 ] | <- Top (Last In, First Out)
| [ 20 ] |
| [ 10 ] |
+--------+Monotonic Stack
Start with an empty stack. We will process array heights [2, 1, 5].
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|---|---|
| Push | O(1) | Insert element on top |
| Pop | O(1) | Remove element from top |
| Peek | O(1) | Query top element without removal |
| Search | O(N) | Requires popping elements |
Production & Real World Applications
- •JavaScript Call Stack: Managing recursive execution frames.
- •Browser Page History: Returning to previous pages on back-click.
Algorithmic Patterns
Maintaining sorted element orders (strictly increasing/decreasing) to find nearest smaller/larger elements.
Pushing open brackets, popping and checking matches on closing brackets.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Stack Overflow (running out of memory during infinite recursions).
- ⚠️Calling pop() on empty stacks (stack underflow).