Data Structures in Practice: Stacks, Queues, and Big-O Intuition
Pick the right container for the job and you get fast, obvious code. Pick the wrong one and your API slows to a crawl as data grows.
Map and Set) when you need to look something up by key instantly. Knowing the cost of each operation - its Big-O - lets you predict how your code behaves at 10 items and at 10 million.
- implement a stack (LIFO) and use it for an undo history;
- implement a queue (FIFO) and use it for a task queue, avoiding the
shift()trap; - use a
Set/Mapfor instant lookup, deduplication, and counting; - read Big-O notation and tell
O(1),O(n), andO(n^2)apart by feel; - replace an accidental
O(n^2)loop with anO(n)hash-map pass.
1. The Stack - last in, first out
A stack is a pile. You add to the top with push and remove from the top with pop. The last thing you put on is the first thing you take off - LIFO (Last In, First Out).
Analogy. Think of a stack of plates. You add a clean plate to the top; the next plate you grab is the one you just added. You never pull a plate from the middle.
Real-world use: undo history. Every text editor keeps an undo stack. Each edit you make is pushed on top. When you press Ctrl+Z, the editor pops the most recent edit and reverses it. Because the newest change is always on top, undo is a single, cheap pop.
In JavaScript a plain array already is a stack: arr.push(x) adds to the end and arr.pop() removes from the end, and both are O(1) - constant time, no matter how big the array is. Wrapping it in a small class just gives the operations clear names:
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); } // remove + return the top
peek() { return this.items[this.items.length - 1]; } // look, do not remove
get size() { return this.items.length; }
}The key discipline: a stack only lets you touch the top. That restriction is a feature - it keeps the structure fast and your intent obvious.