Stack Applications

Stacks are one of the most versatile data structures in computer science. Despite their simple LIFO (Last-In, First-Out) interface — just push and pop — they power an impressive range of algorithms: expression evaluation, syntax checking, monotonic queries, and complex string decoding. This page walks through eight classic stack applications with full JavaScript solutions, key insights, and complexity analysis.

1. Balanced Parentheses

Given a string containing only the characters (, ), [, ], {, and }, determine if the string is valid. A string is valid when every opening bracket is closed by the same type of bracket and in the correct order.

Examples: "()[]{}" → valid, "([)]" → invalid, "{[]}" → valid.

Note

Push every opening bracket onto the stack. When a closing bracket is encountered, the stack top must be its matching opener — if it is not (or the stack is empty), the string is invalid. After processing the whole string, the stack must be empty.

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

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else {
      // It's a closing bracket
      if (stack.length === 0 || stack[stack.length - 1] !== map[char]) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;
}

// Examples
console.log(isValid('()[]{}'));  // true
console.log(isValid('([)]'));    // false
console.log(isValid('{[]}'));    // true
console.log(isValid('('));       // false  — unclosed bracket

Operation	Complexity
Time	O(n) — one pass through the string
Space	O(n) — worst case all openers on the stack

2. Evaluate Postfix Expression

A postfix (Reverse Polish Notation) expression places operators after their operands. Given a postfix expression like "3 4 + 2 *", evaluate it to produce the result (here, 14).

Postfix notation eliminates the need for parentheses — operator precedence is already encoded in the order of tokens.

Note

Scan tokens left to right. When you see a number, push it. When you see an operator, pop the top two numbers, apply the operator, and push the result back. The final answer is the single remaining value on the stack.

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      const b = stack.pop(); // second operand
      const a = stack.pop(); // first operand

      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; // truncate toward zero
      }
    } else {
      stack.push(Number(token));
    }
  }

  return stack[0];
}

// Examples
console.log(evalRPN(['3', '4', '+', '2', '*'])); // 14  → (3+4)*2
console.log(evalRPN(['5', '1', '2', '+', '4', '*', '+', '3', '-'])); // 14
console.log(evalRPN(['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+', '5', '+'])); // 22

Operation	Complexity
Time	O(n) — single pass over tokens
Space	O(n) — stack holds at most n/2 values

3. Infix to Postfix Conversion

Convert a standard infix expression like "a+b*(c-d)" into its postfix equivalent "abcd-*+". This is the basis for how compilers and calculators parse arithmetic expressions.

The Shunting-Yard algorithm (Dijkstra, 1961) handles operator precedence and associativity using a stack of operators.

Note

Assign numeric precedence to each operator. When a new operator arrives, pop all operators from the stack that have equal or higher precedence (left-associative) and append them to the output, then push the new operator. Parentheses are handled as precedence fences — a \`(\` is pushed and acts as a barrier; when a \`)\` is encountered, pop until the matching \`(\`.

function infixToPostfix(expr) {
  const precedence = { '+': 1, '-': 1, '*': 2, '/': 2, '^': 3 };
  const output = [];
  const opStack = [];

  const isOperand = (ch) => /[a-zA-Z0-9]/.test(ch);
  const peek = () => opStack[opStack.length - 1];

  for (const ch of expr.replace(/s/g, '')) {
    if (isOperand(ch)) {
      output.push(ch);
    } else if (ch === '(') {
      opStack.push(ch);
    } else if (ch === ')') {
      while (peek() !== '(') {
        output.push(opStack.pop());
      }
      opStack.pop(); // discard '('
    } else {
      // Operator: pop higher or equal precedence operators first
      // For right-associative operators like '^', use strict '<' comparison
      while (
        opStack.length > 0 &&
        peek() !== '(' &&
        precedence[peek()] >= precedence[ch]
      ) {
        output.push(opStack.pop());
      }
      opStack.push(ch);
    }
  }

  while (opStack.length > 0) {
    output.push(opStack.pop());
  }

  return output.join(' ');
}

// Examples
console.log(infixToPostfix('a+b'));           // 'a b +'
console.log(infixToPostfix('a+b*c'));         // 'a b c * +'
console.log(infixToPostfix('a+b*(c-d)'));     // 'a b c d - * +'
console.log(infixToPostfix('(a+b)*(c+d)'));   // 'a b + c d + *'

Operation	Complexity
Time	O(n) — each token processed at most twice (push + pop)
Space	O(n) — operator stack in the worst case

4. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time. This is a classic interview problem that tests your ability to augment a data structure.

The challenge: a regular stack tracks order but not minimums. Removing the current min could make tracking impossible without a re-scan (O(n)).

Note

Maintain a parallel \`minStack\` alongside the main stack. Whenever you push a value onto the main stack, also push the current minimum (the smaller of the new value and the current min) onto \`minStack\`. When you pop from the main stack, also pop from \`minStack\`. The top of \`minStack\` is always the current minimum.

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = []; // each entry: current min at that depth
  }

  push(val) {
    this.stack.push(val);
    const currentMin =
      this.minStack.length === 0
        ? val
        : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(currentMin);
  }

  pop() {
    this.stack.pop();
    this.minStack.pop();
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

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

// Example usage
const ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
console.log(ms.getMin()); // -3
ms.pop();
console.log(ms.top());    // 0
console.log(ms.getMin()); // -2

Operation	Complexity
push / pop / top / getMin	O(1) — all constant time
Space	O(n) — two stacks, each at most n entries

5. Next Greater Element

Given an array of integers, for each element find the next element to its right that is strictly greater. If no such element exists, the answer for that position is -1.

Example: [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1].

A naive double-loop solution is O(n²). The stack-based approach achieves O(n).

Note

Use a monotonic decreasing stack that stores indices. Iterate through the array. For each element, while the stack is not empty and the current element is greater than the element at the index on top of the stack, that top index has found its "next greater" — pop it and record the answer. Then push the current index. Any indices still on the stack after the full pass have no greater element to their right (-1).

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // stores indices, monotonic decreasing by value

  for (let i = 0; i < nums.length; i++) {
    // Current element is the "next greater" for everything smaller on the stack
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }

  // Remaining indices in stack have no greater element → already -1
  return result;
}

// Example
console.log(nextGreaterElement([2, 1, 2, 4, 3])); // [4, 2, 4, -1, -1]
console.log(nextGreaterElement([1, 3, 2, 4]));     // [3, 4, 4, -1]

// Circular variant (LeetCode 503): search wraps around the array
function nextGreaterElementCircular(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];

  for (let i = 0; i < 2 * n; i++) {
    const val = nums[i % n];
    while (stack.length > 0 && val > nums[stack[stack.length - 1]]) {
      result[stack.pop()] = val;
    }
    if (i < n) stack.push(i);
  }

  return result;
}

console.log(nextGreaterElementCircular([1, 2, 1])); // [2, -1, 2]

Operation	Complexity
Time	O(n) — each element pushed and popped at most once
Space	O(n) — stack and result array

6. Largest Rectangle in Histogram

Given an array heights representing the heights of bars in a histogram (each bar has width 1), find the area of the largest rectangle that can be formed within the histogram.

Example: [2, 1, 5, 6, 2, 3] → 10 (the rectangle over bars at indices 2 and 3, height 5, width 2).

This is one of the most elegant stack applications — the O(n) solution is far from obvious.

Note

Use a stack that keeps indices of bars in strictly increasing height order. When a shorter bar is encountered, every bar on the stack that is taller than the current bar can no longer extend to the right — pop each one and compute its maximum rectangle: the height is that bar's height, and the width extends from the new stack top to the current index. Sentinel values (height 0) at both ends simplify boundary handling.

function largestRectangleInHistogram(heights) {
  // Append a sentinel 0 so all bars are flushed at the end
  const bars = [...heights, 0];
  const stack = [-1]; // sentinel index
  let maxArea = 0;

  for (let i = 0; i < bars.length; i++) {
    // Pop all bars taller than the current bar
    while (stack[stack.length - 1] !== -1 && bars[stack[stack.length - 1]] >= bars[i]) {
      const height = bars[stack.pop()];
      const width = i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}

// Examples
console.log(largestRectangleInHistogram([2, 1, 5, 6, 2, 3])); // 10
console.log(largestRectangleInHistogram([2, 4]));              // 4
console.log(largestRectangleInHistogram([1]));                 // 1
console.log(largestRectangleInHistogram([6, 2, 5, 4, 5, 1, 6])); // 12

/*
  Walk-through for [2,1,5,6,2,3,0]:
  i=0 h=2: push 0         stack: [-1,0]
  i=1 h=1: pop 0 (h=2, w=1-(-1)-1=1, area=2), push 1  stack: [-1,1]
  i=2 h=5: push 2         stack: [-1,1,2]
  i=3 h=6: push 3         stack: [-1,1,2,3]
  i=4 h=2: pop 3 (h=6,w=1,area=6), pop 2 (h=5,w=2,area=10), push 4  stack: [-1,1,4]
  i=5 h=3: push 5         stack: [-1,1,4,5]
  i=6 h=0: pop 5 (h=3,w=1,area=3), pop 4 (h=2,w=4,area=8), pop 1 (h=1,w=6,area=6)
  maxArea = 10
*/

Operation	Complexity
Time	O(n) — each bar pushed and popped exactly once
Space	O(n) — stack holds at most n indices

7. Daily Temperatures

Given an array temperatures, for each day return the number of days you have to wait until a warmer temperature. If there is no future day with a higher temperature, return 0 for that day.

Example: [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0].

This is LeetCode 739 and is a direct application of a monotonic stack on indices.

Note

Maintain a monotonic decreasing stack of indices (decreasing by temperature). For each day \`i\`, while the current temperature is warmer than the temperature at the index on top of the stack, the top index has found its answer: \`i - top\`. Pop and record. Then push \`i\`. Any indices remaining in the stack after the full pass get answer 0 (already the default).

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = []; // monotonic decreasing stack of indices

  for (let i = 0; i < n; i++) {
    while (
      stack.length > 0 &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const prevDay = stack.pop();
      result[prevDay] = i - prevDay;
    }
    stack.push(i);
  }

  return result;
}

// Examples
console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]));
// [1, 1, 4, 2, 1, 1, 0, 0]

console.log(dailyTemperatures([30, 40, 50, 60]));
// [1, 1, 1, 0]

console.log(dailyTemperatures([30, 60, 90]));
// [1, 1, 0]

/*
  Walk-through for [73, 74, 75, 71, 69, 72, 76, 73]:
  i=0 t=73: stack empty, push 0               stack:[0]
  i=1 t=74: 74>73, pop 0, result[0]=1, push 1  stack:[1]
  i=2 t=75: 75>74, pop 1, result[1]=1, push 2  stack:[2]
  i=3 t=71: push 3                             stack:[2,3]
  i=4 t=69: push 4                             stack:[2,3,4]
  i=5 t=72: 72>69, pop 4, result[4]=1
            72>71, pop 3, result[3]=2, push 5  stack:[2,5]
  i=6 t=76: 76>72, pop 5, result[5]=1
            76>75, pop 2, result[2]=4, push 6  stack:[6]
  i=7 t=73: push 7                             stack:[6,7]
  End: indices 6,7 remain → result stays 0
*/

Operation	Complexity
Time	O(n) — each index pushed and popped at most once
Space	O(n) — stack and result array

8. Decode String

Given an encoded string like "3[a2[b]]", return the decoded string "abbaabbabb". The encoding rule is: k[encoded_string] means the encoded_string inside the brackets is repeated k times. You may assume the input is always valid and numbers are positive integers.

Examples: "3[a]2[bc]" → "aaabcbc", "3[a2[c]]" → "accaccacc".

Note

Use two stacks: one for repeat counts (\`countStack\`) and one for accumulated strings (\`stringStack\`). When a digit is seen, build the full number. When \`[\` is seen, push the current count and current string onto their respective stacks, then reset both. When \`]\` is seen, pop the count and previous string — repeat the current string that many times and append it to the previous string. When a letter is seen, append it to the current string.

function decodeString(s) {
  const countStack = [];  // stores repeat counts
  const stringStack = []; // stores accumulated strings before '['
  let currentString = '';
  let currentNum = 0;

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      // Build multi-digit numbers
      currentNum = currentNum * 10 + Number(ch);
    } else if (ch === '[') {
      // Save state and start fresh
      countStack.push(currentNum);
      stringStack.push(currentString);
      currentNum = 0;
      currentString = '';
    } else if (ch === ']') {
      // Restore: repeat currentString, append to previous
      const repeatCount = countStack.pop();
      const prevString = stringStack.pop();
      currentString = prevString + currentString.repeat(repeatCount);
    } else {
      // Regular character
      currentString += ch;
    }
  }

  return currentString;
}

// Examples
console.log(decodeString('3[a]2[bc]'));    // 'aaabcbc'
console.log(decodeString('3[a2[c]]'));     // 'accaccacc'
console.log(decodeString('2[abc]3[cd]ef')); // 'abcabccdcdcdef'
console.log(decodeString('3[a2[b]]'));     // 'abbaabbabb'  ← nested!

/*
  Walk-through for "3[a2[b]]":
  '3': currentNum=3
  '[': push 3 to countStack, push '' to stringStack, reset
       countStack:[3]  stringStack:['']  cur=''
  'a': currentString='a'
  '2': currentNum=2
  '[': push 2, push 'a', reset
       countStack:[3,2]  stringStack:['','a']  cur=''
  'b': currentString='b'
  ']': pop count=2, pop prev='a'
       currentString = 'a' + 'b'.repeat(2) = 'abb'
       countStack:[3]  stringStack:['']
  ']': pop count=3, pop prev=''
       currentString = '' + 'abb'.repeat(3) = 'abbabbabb'
*/

Operation	Complexity
Time	O(n * k) — where k is the maximum nesting repeat factor
Space	O(n) — two stacks proportional to nesting depth

Summary: When to Reach for a Stack

The eight applications above share a common thread: in each case, the stack maintains a meaningful invariant about elements seen so far, allowing deferred decisions to be made efficiently.

Problem	Stack Invariant	Time
Balanced Parentheses	Open brackets awaiting a match	O(n)
Evaluate Postfix	Operands awaiting an operator	O(n)
Infix to Postfix	Operators awaiting lower-precedence context	O(n)
Min Stack	Minimum value at every depth	O(1) per op
Next Greater Element	Elements awaiting a larger right-neighbour	O(n)
Largest Rectangle	Ascending bar indices awaiting a shorter bar	O(n)
Daily Temperatures	Days awaiting a warmer future day	O(n)
Decode String	Outer context saved across bracket levels	O(n·k)

Tip

The monotonic stack pattern (Next Greater Element, Largest Rectangle, Daily Temperatures) is extremely common in competitive programming and interviews. The key question to ask is: for each element, what is the nearest element to its left/right that satisfies some condition? If the answer involves a comparison with earlier unsettled elements, a monotonic stack usually gives you O(n).

Practice Problems

LeetCode 20 — Valid Parentheses (balanced brackets)
LeetCode 150 — Evaluate Reverse Polish Notation
LeetCode 155 — Min Stack
LeetCode 496 — Next Greater Element I
LeetCode 503 — Next Greater Element II (circular)
LeetCode 84 — Largest Rectangle in Histogram
LeetCode 739 — Daily Temperatures
LeetCode 394 — Decode String
LeetCode 42 — Trapping Rain Water (two-pointer or monotonic stack)
LeetCode 85 — Maximal Rectangle (extends histogram problem to 2D)