Stacks & Queues

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;}

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);ms.pop();

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];}

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;}

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('/');}

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);q2.push(3);

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);

//   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".

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;}

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;}

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;}

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';}

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);

//        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);// 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.