📚 Stack
One-line summary: Last-in first-out (LIFO) — O(1) push and pop, the backbone of DFS, expression evaluation, and backtracking.
What is a Stack?
-
pop()— Remove and return top element: O(1) -
peek()/top()— View top element without removing: O(1) -
isEmpty()— Check if stack is empty: O(1)
JavaScript Implementation
// Using built-in array methods (most common)
const stack = [];
stack.push(1); // Add to top
stack.push(2);
const peek = stack[stack.length - 1]; // View top without removing
When to Use Stacks?
✅ Perfect for:
- Function calls (call stack)
- Undo/Redo operations (text editors)
- Expression evaluation (calculators)
- Balanced parentheses checking
- Depth-First Search (DFS) traversal
- Backtracking algorithms
- Browser history (back button)
❌ Not ideal for:
-
Random access to elements
-
Searching through all elements
-
When you need FIFO behavior (use queue instead)## 📊 Visual Learning
Stack Operations Overview
Visual representation of push, pop, peek operations and LIFO (Last In, First Out) principle
Stack Memory Layout
Understanding how stack elements are stored and accessed in memory
Monotonic Stack Applications
| Operation | Time Complexity | Space Complexity | Notes |
|---|
| Pop | O(1) | O(1) | Remove from top | | Peek/Top | O(1) | O(1) | View top element |
1️⃣ Balanced Parentheses - Classic Stack Problem
function isValid(s) {
const stack = [];
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const char of s) {
if ('([{'.includes(char)) {
stack.push(char);
else if (char in pairs) {
if (stack.length === 0 || stack.pop() !== pairs[char]) {
// Use case: Validate parentheses, brackets, braces
2️⃣ Expression Evaluation - Reverse Polish Notation
function evalRPN(tokens) {
const stack = [];
const operators = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
};
for (const token of tokens) {
const b = stack.pop(); // Second operand
const a = stack.pop(); // First operand
stack.push(operators[token](a, b));
stack.push(parseInt(token));
}
}
return stack[0];
const stack = []; // Store indices
for (let i = 0; i < nums.length; i++) {
// While stack not empty and current element > stack top element
while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
const index = stack.pop();
result[index] = nums[i];
}
stack.push(i);
}
return result;
}
// Time: O(n), Space: O(n)
// Use case: Next greater/smaller element problems
4️⃣ Min Stack - Stack with Minimum Tracking
class MinStack {
constructor() {
this.stack = [];
this.minStack = []; // Track minimums
}
push(val) {
this.stack.push(val);
// Push to minStack if it's empty or val is <= current min
if (this.minStack.length === 0 || val <= this.getMin()) {
this.minStack.push(val);
}
}
pop() {
const popped = this.stack.pop();
// If popped element was the minimum, remove from minStack too
if (popped === this.getMin()) {
this.minStack.pop();
}
return popped;
}
top() {
return this.stack[this.stack.length - 1];
}
getMin() {
return this.minStack[this.minStack.length - 1];
}
}
// All operations: O(1) time, O(n) space
// Use case: Stack with additional min/max tracking
5️⃣ Daily Temperatures - Stack for Indices
function dailyTemperatures(temperatures) {
const result = new Array(temperatures.length).fill(0);
const stack = []; // Store indices of temperatures
for (let i = 0; i < temperatures.length; i++) {
// While current temp > temp at stack top index
while (stack.length > 0 &&
temperatures[i] > temperatures[stack[stack.length - 1]]) {
const prevIndex = stack.pop();
result[prevIndex] = i - prevIndex; // Days difference
}
stack.push(i);
}
return result;
}
// Time: O(n), Space: O(n)
// Use case: Finding next warmer day, stock span problems
⚠️ Common Pitfalls & How to Avoid Them
🚫 Empty Stack Operations
// ❌ Wrong - No empty check
const top = stack.pop(); // Could be undefined!
// ✅ Correct - Always check before popping
if (stack.length > 0) {
const top = stack.pop();
}
// ✅ Alternative - Safe peek
const top = stack.length > 0 ? stack[stack.length - 1] : null;
🚫 Stack vs Queue Confusion
// Stack (LIFO) - Last In, First Out
stack.push(1); stack.push(2); stack.push(3);
console.log(stack.pop()); // 3 (last added)
queue.push(1); queue.push(2); queue.push(3);
console.log(queue.shift()); // 1 (first added)
```javascript
if (condition) stack.pop(); // Changes length during loop!
}
// ✅ Correct - Process until empty
while (stack.length > 0) {
const item = stack.pop();
if (condition) {
// Process item
}
}
💡 Pro Tips
- Use descriptive variable names:
operatorStack,parenthesesStack - Consider using a class for complex stack operations
- Remember that JavaScript arrays are dynamic - no size limits
- Use
stack[stack.length - 1]for peek without modifying - Stack overflow can occur with deep recursion (implicit stack)
Practice Problems
🔗 Related Topics
- Monotonic Stack — Specialized stack for next greater/smaller problems
- Recursion — Call stack is an implicit stack
- Graphs — DFS traversal uses explicit stack
- Queue — Complementary FIFO data structure
- Backtracking — Uses stack for state management
🎯 Quick Interview Prep Checklist
- Understand LIFO principle and basic operations
- Master balanced parentheses validation
- Practice expression evaluation problems
- Know monotonic stack patterns (next greater element)
- Understand min/max stack implementations
- Practice stack-based DFS traversals
- Know when to use stack vs queue
- Comfortable with stack simulation problems
← Back to Home · © sparshjaswal