Stacks

Interactive Visualization

Time Complexity

Key Points

• LIFO: Last In, First Out
• Two main operations: push (add to top), pop (remove from top)
• peek: look at top without removing
• JS arrays work as stacks with push/pop
• The call stack is literally a stack!
• Used for: matching brackets, undo/redo, DFS, expression evaluation

Code Examples

// Using array as stack
const stack = []

// Push - add to top - O(1)
stack.push(1)  // [1]
stack.push(2)  // [1, 2]
stack.push(3)  // [1, 2, 3]

// Pop - remove from top - O(1)
stack.pop()    // Returns 3, stack is [1, 2]
stack.pop()    // Returns 2, stack is [1]

// Peek - look at top - O(1)
stack[stack.length - 1]  // 1 (doesn't remove)

// Check if empty
stack.length === 0  // false

function a() {
  console.log('a start')
  b()
  console.log('a end')
}

function b() {
  console.log('b start')
  c()
  console.log('b end')
}

function c() {
  console.log('c')
}

a()
// Call stack grows:    [a] → [a, b] → [a, b, c]
// Then unwinds:        [a, b, c] → [a, b] → [a] → []

// Output:
// a start → b start → c → b end → a end

function isValid(s) {
  const stack = []
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{'
  }

  for (const char of s) {
    if ('([{'.includes(char)) {
      // Opening bracket - push to stack
      stack.push(char)
    } else {
      // Closing bracket - must match top
      if (stack.pop() !== pairs[char]) {
        return false
      }
    }
  }

  return stack.length === 0
}

isValid('([{}])')  // true
isValid('([)]')    // false
isValid('((')      // false

function reverse(str) {
  const stack = []

  // Push all characters
  for (const char of str) {
    stack.push(char)
  }

  // Pop to build reversed string
  let result = ''
  while (stack.length > 0) {
    result += stack.pop()
  }

  return result
}

reverse('hello')  // 'olleh'

// LIFO naturally reverses order!

function evalRPN(tokens) {
  const stack = []

  for (const token of tokens) {
    if ('+-*/'.includes(token)) {
      const b = stack.pop()
      const a = stack.pop()

      switch (token) {
        case '+': stack.push(a + b); break
        case '-': stack.push(a - b); break
        case '*': stack.push(a * b); break
        case '/': stack.push(Math.trunc(a / b)); break
      }
    } else {
      stack.push(Number(token))
    }
  }

  return stack[0]
}

evalRPN(['2', '3', '+', '4', '*'])  // (2+3)*4 = 20

class MinStack {
  constructor() {
    this.stack = []
    this.minStack = []  // Track minimums
  }

  push(val) {
    this.stack.push(val)
    // Push to minStack if empty or <= current min
    if (this.minStack.length === 0 ||
        val <= this.getMin()) {
      this.minStack.push(val)
    }
  }

  pop() {
    const val = this.stack.pop()
    if (val === this.getMin()) {
      this.minStack.pop()
    }
  }

  getMin() {
    return this.minStack[this.minStack.length - 1]
  }
}

// All operations O(1)!

Common Mistakes

• Popping from empty stack (check isEmpty first)
• Using shift/unshift instead of push/pop (O(n) vs O(1))
• Forgetting stack is LIFO when order matters
• Not recognizing stack problems (look for "matching", "nested", "undo")

Interview Tips

• When you see nested structures or matching pairs, think stack
• DFS (depth-first search) can use explicit stack or recursion
• Monotonic stack solves "next greater element" problems
• Stack + queue can simulate other data structures

Practice Problems

Related Concepts