Interview Forge

LINEAR DATA STRUCTURES / ALGORITHM BRIEF

Stack

A stack is a Last-In-First-Out (LIFO) collection.

BeginnerPhase 02 / Topic 3 of 8Mental modelComplexityEdge cases
01

Overview

A stack is a Last-In-First-Out (LIFO) collection. You push onto the top and pop from the top, both in O(1). The most recently added item is always the next one out.

Stacks appear whenever the most recent unfinished thing must be handled first: matching brackets, undoing actions, evaluating expressions, and simulating recursion. The monotonic stack, which keeps elements in sorted order, is its own powerful pattern for next-greater-element problems.

A stack of plates

You always put a clean plate on top and take the top plate when you need one. The plate at the bottom was the first one placed and will be the last one used.

02

When to use it

  • Matching nested pairs: brackets, tags, parentheses.
  • Reversing order, or processing the most recent item first.
  • Evaluating or parsing expressions, including postfix (Reverse Polish Notation).
  • Converting recursion to iteration (DFS with an explicit stack).
  • Undo / redo and navigation history.
03

Problem patterns it solves

Bracket matching

Recognize it when: valid parentheses, balanced tags, minimum insertions to balance.

  • 20. Valid Parentheses
  • 921. Minimum Add to Make Parentheses Valid
  • 1249. Minimum Remove to Make Valid Parentheses
  • 32. Longest Valid Parentheses
Nested decoding / reversal

Recognize it when: process innermost first: decode strings, reverse inside parentheses.

  • 394. Decode String
  • 1190. Reverse Substrings Between Each Pair of Parentheses
  • 71. Simplify Path
Expression evaluation

Recognize it when: calculators, postfix, operator precedence.

  • 150. Evaluate Reverse Polish Notation
  • 224. Basic Calculator
  • 227. Basic Calculator II
Stack with extra state

Recognize it when: track min / max alongside values, or counts for adjacent duplicates.

  • 155. Min Stack
  • 1047. Remove All Adjacent Duplicates In String
  • 1209. Remove All Adjacent Duplicates in String II
  • 735. Asteroid Collision
Simulation

Recognize it when: operations like back, cancel, go up a folder.

  • 682. Baseball Game
  • 1598. Crawler Log Folder
  • 844. Backspace String Compare
Monotonic stack

Recognize it when: next / previous greater or smaller element.

  • 739. Daily Temperatures
  • 496. Next Greater Element I
  • 84. Largest Rectangle in Histogram
04

Where it is used in real software

The call stack

Every program uses a stack to track function calls. Stack traces in error messages print this stack from the most recent call down.

Undo in editors

Each edit is pushed onto an undo stack; undo pops it and pushes it onto a redo stack.

Compilers and parsers

Parsers use stacks to match nested structures and convert infix expressions using the shunting-yard algorithm.

Browser back button

Visiting a page pushes the current page; pressing back pops it.

05

Key terms

push
Add to the top. O(1).
pop
Remove and return the top. O(1).
peek / top
Read the top without removing it. O(1).
LIFO
Last in, first out.
Stack overflow / underflow
Pushing past capacity / popping an empty stack.
06

Valid parentheses algorithm

  1. 1
    Map closers to openers

    { ')': '(', ']': '[', '}': '{' }.

  2. 2
    Push every opener

    An opener starts a new unfinished group.

  3. 3
    On a closer, check the top

    The top must be the matching opener; otherwise the string is invalid.

  4. 4
    Pop the matched opener

    That group is now complete.

  5. 5
    Finish with an empty stack

    Leftover openers mean some groups were never closed.

Stack contents while validating "{[()]}"
Step 1 / 6
{
0
1
2

STEP 1Read '{': an opener, push it.

07

Evaluate Reverse Polish Notation

tokens = ["2", "1", "+", "3", "*"] (means (2 + 1) * 3)

Step 1 / 5
TokenActionStack after
2push[2]
1push[2, 1]
+pop 1 and 2, push 2 + 1[3]
3push[3, 3]
*pop 3 and 3, push 3 * 3[9]

NOWToken: 2 | Action: push | Stack after: [2]

The answer is 9. Pop order matters: the first pop is the right operand, the second is the left, which is important for - and /.

08

Implementation

function isValid(s) {  const pairs = { ")": "(", "]": "[", "}": "{" };  const stack = [];  for (const ch of s) {    if (ch in pairs) {      if (stack.pop() !== pairs[ch]) return false;    } else {      stack.push(ch);    }  }  return stack.length === 0;} function evalRPN(tokens) {  const stack = [];  for (const t of tokens) {    if ("+-*/".includes(t) && t.length === 1) {      const b = stack.pop(), a = stack.pop();      if (t === "+") stack.push(a + b);      else if (t === "-") stack.push(a - b);      else if (t === "*") stack.push(a * b);      else stack.push(Math.trunc(a / b)); // truncate toward zero    } else {      stack.push(Number(t));    }  }  return stack[0];} // 394. Decode String: "3[a2[c]]" -> "accaccacc"function decodeString(s) {  const counts = [], strings = [];  let current = "", k = 0;  for (const ch of s) {    if (ch >= "0" && ch <= "9") k = k * 10 + Number(ch);    else if (ch === "[") { counts.push(k); strings.push(current); current = ""; k = 0; }    else if (ch === "]") current = strings.pop() + current.repeat(counts.pop());    else current += ch;  }  return current;} class MinStack {  constructor() { this.stack = []; this.mins = []; }  push(x) { this.stack.push(x); this.mins.push(Math.min(x, this.mins.at(-1) ?? Infinity)); }  pop() { this.mins.pop(); return this.stack.pop(); }  top() { return this.stack.at(-1); }  getMin() { return this.mins.at(-1); }}
09

Complexity and performance

push / pop / peekO(1)

Array end or linked list head.

Typical problemO(n)

Each element is pushed and popped at most once.

SpaceO(n)

Worst case: everything is pushed.

10

Trade-offs

Array vs linked list backing

Arrays are faster and cache-friendly; linked lists never need resizing. JS arrays and Java ArrayDeque are the usual choices.

Java Stack class

java.util.Stack is synchronized and extends Vector. Use ArrayDeque with push, pop, and peek instead.

Recursion vs explicit stack

An explicit stack avoids stack overflow for deep inputs, at the cost of more code.

11

Variants and related techniques

Two stacks as a queue

An input stack and an output stack give amortized O(1) queue operations.

Monotonic stack

Keep the stack sorted by popping elements that violate the order; answers next-greater queries in O(n).

Stack of pairs

Store [char, count] to collapse runs, as in removing k adjacent duplicates.

12

Common mistakes

  • Popping an empty stack.

    Fix: Check emptiness first; in JS, pop on an empty array returns undefined which can hide bugs.

  • Wrong operand order for - and /.

    Fix: b = pop(), a = pop(), compute a op b.

  • Forgetting leftover elements.

    Fix: Check that the stack is empty at the end of matching problems.

13

Interview questions

How do you implement a queue using stacks?

Push to an input stack. To dequeue, if the output stack is empty, move everything from input to output (reversing the order), then pop from output. Each element moves once, so operations are amortized O(1).

How does Min Stack get the minimum in O(1)?

Keep a second stack where each entry is the minimum of all elements at or below that position. Push and pop both stacks together.

14

Practice problems

ProblemDifficultyWhat it trains
20. Valid ParenthesesEasyBasic matching.
1598. Crawler Log FolderEasySimulation.
155. Min StackMediumAuxiliary state.
150. Evaluate Reverse Polish NotationMediumOperand order.
394. Decode StringMediumNested state with two stacks.
1190. Reverse Substrings Between Each Pair of ParenthesesMediumInnermost first.
224. Basic CalculatorHardSigns and parentheses.