// ─── Stack backed by a JS array ──────────────────────────────
class Stack {
  #items = [];

  push(value) { this.#items.push(value); }     // O(1) amortized
  pop()       { return this.#items.pop(); }     // O(1)
  peek()      { return this.#items.at(-1); }    // O(1) — read top without removing
  isEmpty()   { return this.#items.length === 0; }
  get size()  { return this.#items.length; }
}

// ─── Classic use case: Balanced brackets ─────────────────────
function isBalanced(str) {
  const stack = new Stack();
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of str) {
    if ('([{'.includes(ch)) {
      stack.push(ch);            // Push opening bracket
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false; // Mismatch
    }
  }
  return stack.isEmpty();        // Valid only if nothing left unmatched
}
console.log(isBalanced('({[]})')); // true
console.log(isBalanced('({[})')); // false

// ─── Min Stack — O(1) getMin at all times ────────────────────
class MinStack {
  #stack = [];
  #minStack = []; // Parallel stack tracking minimums

  push(val) {
    this.#stack.push(val);
    const currentMin = this.#minStack.at(-1) ?? Infinity;
    this.#minStack.push(Math.min(val, currentMin)); // Track running min
  }
  pop() {
    this.#minStack.pop();
    return this.#stack.pop();
  }
  peek()   { return this.#stack.at(-1); }
  getMin() { return this.#minStack.at(-1); } // O(1) — no scan needed
}

// ─── Iterative DFS using explicit stack (avoids call stack overflow) ─
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = new Stack();
  stack.push(start);
  while (!stack.isEmpty()) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const neighbor of graph[node] ?? []) stack.push(neighbor);
  }
  return visited;
}