Stack Patterns

Most stack problems fall into one of four templates; recognising the pattern lets you sketch a solution before writing a single line of code.

5 min read Level 2/5 #dsa#stack#patterns

What you'll learn

Identify the four common stack patterns by problem shape
Implement undo/redo with two stacks
Trace function-call mechanics through a manual call-stack simulation

Once you know that a structure is a stack, the next question is which pattern does this problem follow? Almost every stack-based problem is a variation of one of the four templates below.

Pattern 1 — Undo / Redo

Keep two stacks: undoStack holds past states; redoStack holds states that were undone. Every user action pushes the current state onto undoStack and clears redoStack.

class TextEditor {
  #undoStack = [];
  #redoStack = [];
  #text = "";

  type(chars) {
    this.#undoStack.push(this.#text);
    this.#redoStack = [];          // new action clears redo history
    this.#text += chars;
  }

  undo() {
    if (!this.#undoStack.length) return;
    this.#redoStack.push(this.#text);
    this.#text = this.#undoStack.pop();
  }

  redo() {
    if (!this.#redoStack.length) return;
    this.#undoStack.push(this.#text);
    this.#text = this.#redoStack.pop();
  }

  read() { return this.#text; }
}

const ed = new TextEditor();
ed.type("hello");
ed.type(" world");
ed.undo();
console.log(ed.read()); // "hello"
ed.redo();
console.log(ed.read()); // "hello world"

Pattern 2 — Function Call Stack

The JavaScript engine itself uses a stack to track active function calls. When you call a function, a frame is pushed; when it returns, the frame is popped. You can simulate this for custom interpreters or iterative DFS:

// Iterative depth-first traversal using an explicit stack
function dfs(root) {
  const stack = [root];
  const visited = [];

  while (stack.length) {
    const node = stack.pop();         // most-recently-discovered first
    visited.push(node.val);
    for (const child of node.children) {
      stack.push(child);
    }
  }

  return visited;
}

Replacing a recursive DFS with an explicit stack avoids call-stack overflow on deep graphs and gives you fine-grained control over traversal order.

Pattern 3 — Expression Evaluation

Operators and operands arrive in a stream. The stack holds operands (or sub-expressions) until an operator arrives and collapses the top items into a single value.

// Evaluate a Reverse Polish Notation expression
function evalRPN(tokens) {
  const stack = [];
  const ops = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "*": (a, b) => a * b,
    "/": (a, b) => Math.trunc(a / b),
  };

  for (const t of tokens) {
    if (ops[t]) {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(ops[t](a, b));
    } else {
      stack.push(Number(t));
    }
  }

  return stack[0];
}

console.log(evalRPN(["2", "1", "+", "3", "*"])); // (2+1)*3 = 9

Pattern 4 — “Last Unmatched” / Nesting

Whenever you encounter an opening token (bracket, tag, parenthesis), push it. When you encounter the matching closing token, pop and compare. If the stack is empty at the end, every opener was matched.

This is the template behind balanced-parentheses, HTML-tag validation, and nested-comment detection. The next lesson builds it out fully.

Pattern	Push when	Pop when
Undo/Redo	user acts	user undoes
Call stack	function is called	function returns
Expression eval	operand arrives	operator arrives
Last unmatched	opener seen	closer seen

Up Next

Apply the “last unmatched” pattern to the classic balanced-parentheses problem, with a complete O(n) implementation.

Balanced Parentheses →