Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Stacks and Queues

Stacks in JavaScript

Written by Updated

A stack is an array where you agree only to touch the end. That restriction is the whole value - it makes the structure O(1) at everything it does, and it makes certain problems obvious.

Last in, first out

You add to the top and remove from the top. The last thing in is the first thing out, like a stack of plates.

In JavaScript you do not need a class. An array with only push and pop is a stack, and both are O(1) because nothing else moves.

A stack, and a stack with a name

javascript

// Perfectly good stack.
const stack = []
stack.push(1)
stack.push(2)
stack.pop()          // 2
stack[stack.length - 1]  // peek at the top

// The same thing, when clarity matters more than brevity.
class Stack {
  #items = []

  push(value) { this.#items.push(value) }
  pop() { return this.#items.pop() }
  peek() { return this.#items[this.#items.length - 1] }
  get size() { return this.#items.length }
  get isEmpty() { return this.#items.length === 0 }
}

const demoStack = new Stack()
demoStack.push(1)
demoStack.push(2)
console.log(demoStack.pop())   // 2
console.log(demoStack.size)    // 1

Shape 1: matching pairs

Anything with opening and closing symbols is a stack. Push what opens, pop when something closes, and check it matches.

Balanced brackets

javascript

function isBalanced(s) {
  const closing = { ")": "(", "]": "[", "}": "{" }
  const stack = []

  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch)
    } else if (closing[ch]) {
      // Nothing to close, or closes the wrong thing.
      if (stack.pop() !== closing[ch]) return false
    }
  }

  // Anything left open means unbalanced.
  return stack.length === 0
}

console.log(isBalanced("{[()]}"))   // true
console.log(isBalanced("{[(])}"))   // false

The final length === 0 check is the one people forget. Without it "(((" passes.

Shape 2: undo, or going back

Browser history, undo in an editor, backtracking through a maze - all stacks. Each step pushes state; going back pops it.

Shape 3: the next bigger thing

This one is less obvious and appears constantly. A monotonic stack finds, for each element, the next element larger than it - in one pass.

Next greater element

javascript

function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1)
  const stack = []   // holds indices, values decreasing

  for (let i = 0; i < nums.length; i++) {
    // Everything smaller than nums[i] has found its answer.
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()] = nums[i]
    }
    stack.push(i)
  }

  return result
}

console.log(nextGreater([2, 1, 2, 4, 3]))  // [4, 2, 4, -1, -1]

The nested while is not quadratic: every index is pushed once and popped at most once, so the whole thing is O(n).

The stack you are already using

Function calls are a stack. That is what a stack overflow is, and why recursion has a depth limit - covered properly in the recursion section.

PreviousThe Sliding Window TechniqueNextQueues in JavaScript