Stacks & The Monotonic Stack Pattern

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Last-In-First-Out (LIFO)

A Stack is an abstract linear data structure that restricts insertions and deletions to a single end called the top:

• push(x): Place item onto top of stack ($O(1)$).
• pop(): Remove and return topmost item ($O(1)$).
• peek(): Inspect topmost item without removing ($O(1)$).

2. Classic Problem: Valid Parentheses

Verify that all opening brackets have corresponding matching closing brackets in the correct order:

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

  for (const char of s) {
    if (char === "(" || char === "{" || char === "[") {
      stack.push(char); // Push opening brackets
    } else if (bracketMap[char]) {
      // Pop matching bracket from top of stack
      if (stack.pop() !== bracketMap[char]) {
        return false;
      }
    }
  }

  return stack.length === 0; // Stack must be completely empty!
}

console.log(isValidParentheses("({[]})")); // Output: true
console.log(isValidParentheses("([)]"));   // Output: false

3. The Monotonic Stack Pattern

A Monotonic Stack keeps its elements in strictly ascending or descending order. It solves "Next Greater Element" and "Daily Temperatures" problems in linear $O(N)$ time!

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // Stores indices of elements

  for (let i = 0; i < nums.length; i++) {
    // While current element is greater than element at top of stack
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const prevIndex = stack.pop();
      result[prevIndex] = nums[i]; // Found next greater element!
    }
    stack.push(i);
  }

  return result;
}

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

4. Common Mistakes

• Forgetting Stack Emptiness Check: Calling pop() on an empty stack returns undefined, which can cause subtle comparison bugs if not guarded.
• Forgetting Final Stack Check: In parentheses matching, if brackets remain unclosed (e.g. "(()"), returning true is wrong. Check stack.length === 0.

5. Next Steps

Use stacks for nested evaluations and parser syntax trees. Next, let's explore Queues, Deques, and Ring Buffers!