Introduction to Stacks

Stacks appear in function calls, undo and redo histories, and expression evaluation. The useful rule is LIFO, or Last In, First Out: the most recently added item is removed first.

LIFO in practice

A stack exposes operations at one end. The stack removes the last item added first. This order is useful when the newest state must take priority over older state. When I first implemented a stack, I kept it simple:

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

I find stacks useful when the newest item determines the next action. Matching brackets is one example:

function isValidParentheses(s) {
  const stack = [];
  const pairs = { "(": ")", "[": "]", "{": "}" };

  for (let char of s) {
    if (pairs[char]) {
      stack.push(char); // Opening bracket
    } else {
      if (stack.length === 0) return false;
      const last = stack.pop();
      if (pairs[last] !== char) return false;
    }
  }

  return stack.length === 0;
}

To reverse an order, I push each item and pop them later:

function reverseString(str) {
  const stack = [];
  for (let char of str) {
    stack.push(char);
  }

  let reversed = "";
  while (stack.length > 0) {
    reversed += stack.pop();
  }
  return reversed;
}

For undo behavior, I store previous states in a stack:

class Editor {
  constructor() {
    this.content = "";
    this.undoStack = [];
  }

  type(text) {
    this.undoStack.push(this.content); // Save state
    this.content += text;
  }

  undo() {
    if (this.undoStack.length > 0) {
      this.content = this.undoStack.pop();
    }
  }
}

When I first learned about stack overflow errors, I thought they were related to the website. The programming error occurs when a stack runs out of space, often because recursion goes too deep. The website name is a programming joke.

Complexity and fit

Stacks have become one of my favorite data structures because the LIFO rule handles nested structures and "most recent" state without extra ordering logic. For a stack that uses a dynamic array, push is amortized O(1) and pop is O(1).

When a problem asks for the latest item, nested matching, reversal, or undo behavior, a stack is a natural candidate. The data structure is small, but its ordering rule removes a lot of bookkeeping.