// ─────────────────────────────────────────────────────────────────────────────
// STACKS & QUEUES
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : LIFO (stack) for nesting / "most recent unresolved"; FIFO (queue) for order / BFS.
// TELL   : "balanced / matching", "nested", "evaluate expression", "undo", "next greater / smaller",
//          "span", "histogram", "first-in-first-out", "level by level".
// SAY    : stack, queue, deque, monotonic stack (increasing / decreasing), amortized O(1),
//          circular buffer / ring buffer, two-stack queue.
// BIG-O  : O(1) push/pop; monotonic stack is O(n) total because each index is pushed/popped once.
// NOTE   : JS Array.shift() is O(n). For a real queue use a head index (section 12) or a linked list.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Valid parentheses  —  push openers; on closer, top must match  —  O(n) / O(n)
function isValid(s) {
  const pair = { ')': '(', ']': '[', '}': '{' }, st = [];
  for (const c of s) {
    if (c in pair) { if (st.pop() !== pair[c]) return false; }
    else st.push(c);
  }
  return st.length === 0;
}
assert.equal(isValid('()[]{}'), true);
assert.equal(isValid('([)]'), false);
assert.equal(isValid(''), true);
assert.equal(isValid('('), false);

// ── 2. Min stack  —  parallel stack of running minimums  —  O(1) all ops / O(n)
class MinStack {
  #s = []; #min = [];
  push(x) { this.#s.push(x); this.#min.push(this.#min.length ? Math.min(x, this.#min[this.#min.length - 1]) : x); }
  pop() { this.#min.pop(); return this.#s.pop(); }
  top() { return this.#s[this.#s.length - 1]; }
  getMin() { return this.#min[this.#min.length - 1]; }
}
const ms = new MinStack();
ms.push(-2); ms.push(0); ms.push(-3);
assert.equal(ms.getMin(), -3);
ms.pop();
assert.equal(ms.top(), 0);
assert.equal(ms.getMin(), -2);

// ── 3. Evaluate reverse polish notation  —  push numbers; operator pops two (b then a)  —  O(n) / O(n)
function evalRPN(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[0];
}
assert.equal(evalRPN(['2', '1', '+', '3', '*']), 9);
assert.equal(evalRPN(['4', '13', '5', '/', '+']), 6);
assert.equal(evalRPN(['-7']), -7);

// ── 4. Decode string  —  stacks for count and partial string; on ']' pop and repeat  —  O(output) / O(n)
function decodeString(s) {
  const counts = [], strs = [];
  let cur = '', k = 0;
  for (const c of s) {
    if (c >= '0' && c <= '9') k = k * 10 + Number(c);
    else if (c === '[') { counts.push(k); strs.push(cur); cur = ''; k = 0; }
    else if (c === ']') cur = strs.pop() + cur.repeat(counts.pop());
    else cur += c;
  }
  return cur;
}
assert.equal(decodeString('3[a]2[bc]'), 'aaabcbc');
assert.equal(decodeString('3[a2[c]]'), 'accaccacc');
assert.equal(decodeString('abc'), 'abc');

// ── 5. Simplify path (Unix)  —  split on '/', '..' pops, '.'/'' skipped  —  O(n) / O(n)
function simplifyPath(path) {
  const st = [];
  for (const part of path.split('/')) {
    if (part === '..') st.pop();
    else if (part && part !== '.') st.push(part);
  }
  return '/' + st.join('/');
}
assert.equal(simplifyPath('/a/./b/../../c/'), '/c');
assert.equal(simplifyPath('/../'), '/');
assert.equal(simplifyPath('/home//foo/'), '/home/foo');

// ── 6. Queue via two stacks  —  inbox push; outbox pop; refill outbox by reversing inbox when empty  —  amortized O(1)
class QueueViaStacks {
  #in = []; #out = [];
  push(x) { this.#in.push(x); }
  #shift() { if (this.#out.length === 0) while (this.#in.length) this.#out.push(this.#in.pop()); }
  pop() { this.#shift(); return this.#out.pop(); }
  peek() { this.#shift(); return this.#out[this.#out.length - 1]; }
  get empty() { return this.#in.length + this.#out.length === 0; }
}
const q2 = new QueueViaStacks();
q2.push(1); q2.push(2);
assert.equal(q2.peek(), 1);
assert.equal(q2.pop(), 1);
q2.push(3);
assert.deepEqual([q2.pop(), q2.pop(), q2.empty], [2, 3, true]);

// ── 7. Stack via one queue  —  after push, rotate the queue size-1 times so the new item is at the front  —  O(n) push, O(1) pop
class StackViaQueue {
  #q = [];
  push(x) { this.#q.push(x); for (let i = 1; i < this.#q.length; i++) this.#q.push(this.#q.shift()); }
  pop() { return this.#q.shift(); }
  top() { return this.#q[0]; }
}
const sq = new StackViaQueue();
sq.push(1); sq.push(2); sq.push(3);
assert.equal(sq.top(), 3);
assert.deepEqual([sq.pop(), sq.pop(), sq.pop()], [3, 2, 1]);

// ── MONOTONIC STACK TEMPLATE (next greater to the right; stack holds INDICES with decreasing values)
//   for i in 0..n-1:
//     while stack not empty and a[stack.top] < a[i]:      // a[i] is the "next greater" for stack.top
//       j = stack.pop(); answer[j] = i (or a[i], or i - j)
//     stack.push(i)
//   leftover indices have no next greater.
//   Flip '<' to '>' for next smaller; iterate from the right for "previous" instead of "next".

// ── 8. Next greater element (circular optional)  —  template, output values  —  O(n) / O(n)
function nextGreater(a) {
  const out = new Array(a.length).fill(-1), st = [];
  for (let i = 0; i < a.length; i++) {
    while (st.length && a[st[st.length - 1]] < a[i]) out[st.pop()] = a[i];
    st.push(i);
  }
  return out;
}
assert.deepEqual(nextGreater([2, 1, 2, 4, 3]), [4, 2, 4, -1, -1]);
assert.deepEqual(nextGreater([3, 2, 1]), [-1, -1, -1]);
assert.deepEqual(nextGreater([]), []);

// ── 9. Daily temperatures  —  template, output distance i - j  —  O(n) / O(n)
function dailyTemperatures(t) {
  const out = new Array(t.length).fill(0), st = [];
  for (let i = 0; i < t.length; i++) {
    while (st.length && t[st[st.length - 1]] < t[i]) { const j = st.pop(); out[j] = i - j; }
    st.push(i);
  }
  return out;
}
assert.deepEqual(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0]);
assert.deepEqual(dailyTemperatures([30, 30]), [0, 0]);

// ── 10. Largest rectangle in histogram  —  increasing stack; on pop, width = i - stack.top - 1; sentinel 0 at end  —  O(n) / O(n)
function largestRectangleArea(h) {
  const st = [];
  let best = 0;
  for (let i = 0; i <= h.length; i++) {
    const cur = i === h.length ? 0 : h[i]; // sentinel flushes the stack
    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;
}
assert.equal(largestRectangleArea([2, 1, 5, 6, 2, 3]), 10);
assert.equal(largestRectangleArea([2, 4]), 4);
assert.equal(largestRectangleArea([]), 0);

// ── 11. Remove k digits (smallest result)  —  increasing stack; pop while top > digit and k > 0; trim; strip leading zeros  —  O(n) / O(n)
function removeKdigits(num, k) {
  const st = [];
  for (const d of num) {
    while (k > 0 && st.length && st[st.length - 1] > d) { st.pop(); k--; }
    st.push(d);
  }
  st.length -= k; // still have removals left: drop from the end
  return st.join('').replace(/^0+/, '') || '0';
}
assert.equal(removeKdigits('1432219', 3), '1219');
assert.equal(removeKdigits('10200', 1), '200');
assert.equal(removeKdigits('10', 2), '0');

// ── 12. Circular queue (ring buffer)  —  fixed array; head/tail indices mod capacity  —  O(1) / O(k)
class CircularQueue {
  #a; #head = 0; #size = 0;
  constructor(k) { this.#a = new Array(k); }
  enqueue(x) { if (this.isFull()) return false; this.#a[(this.#head + this.#size) % this.#a.length] = x; this.#size++; return true; }
  dequeue() { if (this.isEmpty()) return false; this.#head = (this.#head + 1) % this.#a.length; this.#size--; return true; }
  front() { return this.isEmpty() ? -1 : this.#a[this.#head]; }
  rear() { return this.isEmpty() ? -1 : this.#a[(this.#head + this.#size - 1) % this.#a.length]; }
  isEmpty() { return this.#size === 0; }
  isFull() { return this.#size === this.#a.length; }
}
const cq = new CircularQueue(3);
assert.deepEqual([cq.enqueue(1), cq.enqueue(2), cq.enqueue(3), cq.enqueue(4)], [true, true, true, false]);
assert.equal(cq.rear(), 3);
assert.equal(cq.dequeue(), true);
assert.deepEqual([cq.enqueue(4), cq.front(), cq.rear()], [true, 2, 4]); // wrapped around

// ── 13. O(1) queue in JS (head-index trick)  —  never shift(); advance head; optionally compact  —  O(1) amortized
//        SAY: "Array.shift is O(n) because V8 re-indexes; I keep a head pointer instead."
class Queue {
  #a = []; #h = 0;
  push(x) { this.#a.push(x); }
  shift() {
    const x = this.#a[this.#h++];
    if (this.#h > 1024 && this.#h * 2 > this.#a.length) { this.#a = this.#a.slice(this.#h); this.#h = 0; } // compact
    return x;
  }
  get length() { return this.#a.length - this.#h; }
}
const q = new Queue();
for (let i = 0; i < 5; i++) q.push(i);
assert.deepEqual([q.shift(), q.shift(), q.length], [0, 1, 3]);
// Deque with array: push/pop O(1) at tail; unshift/shift O(n) at head. For a true O(1) deque use a doubly linked list
// or two arrays (front stack + back stack). For "sliding window max" a plain array + head index is enough.

console.log('ok: algorithms/stacks-queues.js');