Stacks & Queues

function nextGreater(nums) {
  const res = Array(nums.length).fill(-1);
  const st = [];
  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[i] > nums[st[st.length - 1]]) res[st.pop()] = nums[i];
    st.push(i);
  }
  return res;
}

class MyQueue {
  constructor() { this.inbox = []; this.outbox = []; }
  push(x) { this.inbox.push(x); }
  pop() { this.peek(); return this.outbox.pop(); }
  peek() {
    if (!this.outbox.length) while (this.inbox.length) this.outbox.push(this.inbox.pop());
    return this.outbox[this.outbox.length - 1];
  }
  empty() { return !this.inbox.length && !this.outbox.length; }
}

class MinStack {
  constructor() { this.s = []; }
  push(x) { this.s.push([x, this.s.length ? Math.min(x, this.getMin()) : x]); }
  pop() { this.s.pop(); }
  top() { return this.s[this.s.length - 1][0]; }
  getMin() { return this.s[this.s.length - 1][1]; }
}

class Stack {
  #a = [];
  push(x) { this.#a.push(x); }
  pop() { return this.#a.pop(); }
  peek() { return this.#a[this.#a.length - 1]; }
  isEmpty() { return this.#a.length === 0; }
  size() { return this.#a.length; }
}

class Queue {
  constructor(cap = 1024) { this.a = new Array(cap); this.head = 0; this.tail = 0; this.count = 0; this.cap = cap; }
  enqueue(x) { if (this.count === this.cap) throw new Error('full'); this.a[this.tail] = x; this.tail = (this.tail + 1) % this.cap; this.count++; }
  dequeue() { if (!this.count) return undefined; const x = this.a[this.head]; this.head = (this.head + 1) % this.cap; this.count--; return x; }
  front() { return this.count ? this.a[this.head] : undefined; }
  isEmpty() { return this.count === 0; }
}

class TwoStacks {
  constructor(n) { this.a = new Array(n); this.top1 = -1; this.top2 = n; }
  push1(x) { if (this.top1 + 1 === this.top2) throw new Error('full'); this.a[++this.top1] = x; }
  push2(x) { if (this.top2 - 1 === this.top1) throw new Error('full'); this.a[--this.top2] = x; }
  pop1() { return this.top1 >= 0 ? this.a[this.top1--] : undefined; }
  pop2() { return this.top2 < this.a.length ? this.a[this.top2++] : undefined; }
}

class MiddleStack {
  constructor() { this.head = null; this.mid = null; this.count = 0; }
  push(x) {
    const node = { val: x, prev: null, next: this.head };
    if (this.head) this.head.prev = node;
    this.head = node;
    this.count++;
    if (this.count === 1) this.mid = node;
    else if (this.count % 2 === 1) this.mid = this.mid.prev;
  }
  pop() {
    if (!this.count) return undefined;
    const x = this.head.val;
    this.head = this.head.next;
    if (this.head) this.head.prev = null;
    this.count--;
    if (this.count % 2 === 0) this.mid = this.mid ? this.mid.next : null;
    return x;
  }
  findMiddle() { return this.mid ? this.mid.val : undefined; }
}

function findCelebrity(n, knows) {
  let cand = 0;
  for (let i = 1; i < n; i++) if (knows(cand, i)) cand = i;
  for (let i = 0; i < n; i++) {
    if (i === cand) continue;
    if (knows(cand, i) || !knows(i, cand)) return -1;
  }
  return cand;
}

function evalPostfix(tokens) {
  const st = [];
  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 (t in ops) { const b = st.pop(), a = st.pop(); st.push(ops[t](a, b)); }
    else st.push(Number(t));
  }
  return st.pop();
}

function evalInfix(expr) {
  const nums = [], ops = [];
  const prec = (o) => (o === '+' || o === '-' ? 1 : o === '*' || o === '/' ? 2 : 0);
  const apply = () => {
    const b = nums.pop(), a = nums.pop(), o = ops.pop();
    nums.push(o === '+' ? a + b : o === '-' ? a - b : o === '*' ? a * b : Math.trunc(a / b));
  };
  const tokens = expr.match(/\d+|[()+\-*/]/g) || [];
  for (const t of tokens) {
    if (/\d/.test(t)) nums.push(Number(t));
    else if (t === '(') ops.push(t);
    else if (t === ')') { while (ops[ops.length - 1] !== '(') apply(); ops.pop(); }
    else { while (ops.length && prec(ops[ops.length - 1]) >= prec(t)) apply(); ops.push(t); }
  }
  while (ops.length) apply();
  return nums[0];
}

function insertAtBottom(stack, x) {
  if (stack.length === 0) { stack.push(x); return; }
  const top = stack.pop();
  insertAtBottom(stack, x);
  stack.push(top);
}

function reverseStack(stack) {
  if (stack.length === 0) return;
  const top = stack.pop();
  reverseStack(stack);
  insertAtBottom(stack, top);
}
function insertAtBottom(stack, x) {
  if (!stack.length) { stack.push(x); return; }
  const t = stack.pop();
  insertAtBottom(stack, x);
  stack.push(t);
}

function sortStack(s) {
  if (s.length === 0) return;
  const top = s.pop();
  sortStack(s);
  sortedInsert(s, top);
}
function sortedInsert(s, x) {
  if (!s.length || s[s.length - 1] <= x) { s.push(x); return; }
  const t = s.pop();
  sortedInsert(s, x);
  s.push(t);
}

function largestRectangleArea(h) {
  const st = [];
  let best = 0;
  for (let i = 0; i <= h.length; i++) {
    const cur = i === h.length ? 0 : h[i];
    while (st.length && h[st[st.length - 1]] >= cur) {
      const height = h[st.pop()];
      const width = st.length ? i - st[st.length - 1] - 1 : i;
      best = Math.max(best, height * width);
    }
    st.push(i);
  }
  return best;
}

function longestValidParentheses(s) {
  const st = [-1];
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') st.push(i);
    else {
      st.pop();
      if (st.length === 0) st.push(i);
      else best = Math.max(best, i - st[st.length - 1]);
    }
  }
  return best;
}

function hasRedundantBrackets(expr) {
  const st = [];
  for (const c of expr) {
    if (c === ')') {
      let hasOp = false;
      while (st.length && st[st.length - 1] !== '(') {
        if ('+-*/'.includes(st.pop())) hasOp = true;
      }
      st.pop(); // '('
      if (!hasOp) return true;
    } else st.push(c);
  }
  return false;
}

class StackViaQueue {
  #q = [];
  push(x) { this.#q.push(x); for (let i = 0; i < this.#q.length - 1; i++) this.#q.push(this.#q.shift()); }
  pop() { return this.#q.shift(); }
  top() { return this.#q[0]; }
  empty() { return this.#q.length === 0; }
}

function isStackPermutation(input, output) {
  const st = [];
  let j = 0;
  for (const x of input) {
    st.push(x);
    while (st.length && st[st.length - 1] === output[j]) { st.pop(); j++; }
  }
  return st.length === 0 && j === output.length;
}

class CircularQueue {
  constructor(k) { this.a = new Array(k); this.k = k; this.head = 0; this.count = 0; }
  enqueue(x) { if (this.count === this.k) return false; this.a[(this.head + this.count) % this.k] = x; this.count++; return true; }
  dequeue() { if (!this.count) return false; this.head = (this.head + 1) % this.k; this.count--; return true; }
  front() { return this.count ? this.a[this.head] : -1; }
  rear() { return this.count ? this.a[(this.head + this.count - 1) % this.k] : -1; }
  isFull() { return this.count === this.k; }
  isEmpty() { return this.count === 0; }
}

class LRUCache {
  constructor(capacity) { this.cap = capacity; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, v);
    return v;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size === this.cap) this.map.delete(this.map.keys().next().value);
    this.map.set(key, value);
  }
}

function reverseFirstK(queue, k) {
  const st = [];
  for (let i = 0; i < k; i++) st.push(queue.shift());
  while (st.length) queue.push(st.pop());
  for (let i = 0; i < queue.length - k; i++) queue.push(queue.shift());
  return queue;
}

function interleaveQueue(q) {
  const half = q.length / 2;
  const st = [];
  for (let i = 0; i < half; i++) st.push(q.shift());
  while (st.length) q.push(st.pop());
  for (let i = 0; i < half; i++) q.push(q.shift());
  for (let i = 0; i < half; i++) { st.push(q.shift()); }
  const res = [];
  for (let i = 0; i < half; i++) { res.push(st.shift()); res.push(q.shift()); }
  q.push(...res);
  return q;
}

function firstTour(pumps) { // pumps[i] = [petrol, distance]
  let start = 0, tank = 0, total = 0;
  for (let i = 0; i < pumps.length; i++) {
    const diff = pumps[i][0] - pumps[i][1];
    tank += diff;
    total += diff;
    if (tank < 0) { start = i + 1; tank = 0; }
  }
  return total >= 0 ? start : -1;
}

function orangesRotting(grid) {
  const R = grid.length, C = grid[0].length;
  let fresh = 0;
  const q = [];
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 2) q.push([r, c, 0]);
      else if (grid[r][c] === 1) fresh++;
    }
  let time = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length) {
    const [r, c, t] = q.shift();
    time = Math.max(time, t);
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] === 1) {
        grid[nr][nc] = 2; fresh--; q.push([nr, nc, t + 1]);
      }
    }
  }
  return fresh === 0 ? time : -1;
}

function nearestOne(grid) {
  const R = grid.length, C = grid[0].length;
  const dist = Array.from({ length: R }, () => Array(C).fill(-1));
  const q = [];
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (grid[r][c] === 1) { dist[r][c] = 0; q.push([r, c]); }
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let head = 0;
  while (head < q.length) {
    const [r, c] = q[head++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < R && nc < C && dist[nr][nc] === -1) {
        dist[nr][nc] = dist[r][c] + 1;
        q.push([nr, nc]);
      }
    }
  }
  return dist;
}

function firstNegativeEachWindow(a, k) {
  const dq = [], res = [];
  for (let i = 0; i < a.length; i++) {
    if (a[i] < 0) dq.push(i);
    if (i >= k - 1) {
      while (dq.length && dq[0] <= i - k) dq.shift();
      res.push(dq.length ? a[dq[0]] : 0);
    }
  }
  return res;
}

function sumOfMinMax(a, k) {
  const maxDq = [], minDq = [];
  let sum = 0;
  for (let i = 0; i < a.length; i++) {
    while (maxDq.length && a[maxDq[maxDq.length - 1]] <= a[i]) maxDq.pop();
    while (minDq.length && a[minDq[minDq.length - 1]] >= a[i]) minDq.pop();
    maxDq.push(i); minDq.push(i);
    if (maxDq[0] <= i - k) maxDq.shift();
    if (minDq[0] <= i - k) minDq.shift();
    if (i >= k - 1) sum += a[maxDq[0]] + a[minDq[0]];
  }
  return sum;
}

function minStringValue(s, k) {
  const freq = new Array(26).fill(0);
  for (const c of s) freq[c.charCodeAt(0) - 97]++;
  for (let i = 0; i < k; i++) {
    let mx = 0;
    for (let j = 1; j < 26; j++) if (freq[j] > freq[mx]) mx = j;
    if (freq[mx] === 0) break;
    freq[mx]--;
  }
  return freq.reduce((acc, f) => acc + f * f, 0);
}

function nextSmaller(a) {
  const res = Array(a.length).fill(-1);
  const st = [];
  for (let i = 0; i < a.length; i++) {
    while (st.length && a[st[st.length - 1]] > a[i]) res[st.pop()] = a[i];
    st.push(i);
  }
  return res;
}

const reverseWithStack = (s) => { const st = [...s]; let r = ''; while (st.length) r += st.pop(); return r; };

function isBalanced(s) {
  const pair = { ')': '(', ']': '[', '}': '{' }, st = [];
  for (const c of s) {
    if ('([{'.includes(c)) st.push(c);
    else if (st.pop() !== pair[c]) return false;
  }
  return st.length === 0;
}

function reverseQueue(q) {
  if (q.length === 0) return;
  const front = q.shift();
  reverseQueue(q);
  q.push(front);
}

function dailyTemperatures(t) {
  const res = new Array(t.length).fill(0), st = [];
  for (let i = 0; i < t.length; i++) {
    while (st.length && t[i] > t[st[st.length - 1]]) {
      const j = st.pop();
      res[j] = i - j;
    }
    st.push(i);
  }
  return res;
}

function nextGreaterElements(nums) {
  const n = nums.length, res = new Array(n).fill(-1), st = [];
  for (let i = 0; i < 2 * n; i++) {
    const x = nums[i % n];
    while (st.length && x > nums[st[st.length - 1]]) res[st.pop()] = x;
    if (i < n) st.push(i);
  }
  return res;
}

function decodeString(s) {
  const st = [];
  let cur = '', num = 0;
  for (const c of s) {
    if (c >= '0' && c <= '9') num = num * 10 + Number(c);
    else if (c === '[') { st.push([cur, num]); cur = ''; num = 0; }
    else if (c === ']') { const [prev, k] = st.pop(); cur = prev + cur.repeat(k); }
    else cur += c;
  }
  return cur;
}

function asteroidCollision(asteroids) {
  const st = [];
  for (const a of asteroids) {
    let alive = true;
    while (alive && a < 0 && st.length && st[st.length - 1] > 0) {
      const top = st[st.length - 1];
      if (top < -a) st.pop();
      else { if (top === -a) st.pop(); alive = false; }
    }
    if (alive) st.push(a);
  }
  return st;
}

class StockSpanner {
  constructor() { this.st = []; }
  next(price) {
    let span = 1;
    while (this.st.length && this.st[this.st.length - 1][0] <= price) span += this.st.pop()[1];
    this.st.push([price, span]);
    return span;
  }
}

function shortestSubarray(nums, k) {
  const n = nums.length, pre = [0];
  for (const x of nums) pre.push(pre[pre.length - 1] + x);
  const dq = []; let head = 0, best = Infinity;
  for (let i = 0; i <= n; i++) {
    while (head < dq.length && pre[i] - pre[dq[head]] >= k) best = Math.min(best, i - dq[head++]);
    while (dq.length > head && pre[dq[dq.length - 1]] >= pre[i]) dq.pop();
    dq.push(i);
  }
  return best === Infinity ? -1 : best;
}