Stack និង Queue

push(1)   push(2)   push(3)   pop() -> 3   pop() -> 2
                     [3]                    
           [2]       [2]       [2]
 [1]       [1]       [1]       [1]          [1]

class Stack<T> {
  private items: T[] = [];

  get size(): number {
    return this.items.length;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  push(value: T): void {
    this.items.push(value);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }
}

const s = new Stack<string>();
s.push("a");
s.push("b");
s.push("c");

console.log(s.peek(), s.pop(), s.size); // c c 2

state:  "Hi there"        undo stack: ["", "Hi"]     redo stack: []
undo -> "Hi"              undo stack: [""]           redo stack: ["Hi there"]
undo -> ""                undo stack: []             redo stack: ["Hi there", "Hi"]
redo -> "Hi"              undo stack: [""]           redo stack: ["Hi there"]

class History<T> {
  private undoStack = new Stack<T>();
  private redoStack = new Stack<T>();

  constructor(private current: T) {}

  get value(): T {
    return this.current;
  }

  set(next: T): void {
    this.undoStack.push(this.current);
    this.current = next;
    this.redoStack = new Stack<T>(); // a new edit clears redo
  }

  undo(): T {
    if (!this.undoStack.isEmpty()) {
      this.redoStack.push(this.current);
      this.current = this.undoStack.pop()!;
    }
    return this.current;
  }

  redo(): T {
    if (!this.redoStack.isEmpty()) {
      this.undoStack.push(this.current);
      this.current = this.redoStack.pop()!;
    }
    return this.current;
  }
}

const h = new History("");
h.set("Hi");
h.set("Hi there");

console.log(h.undo(), h.undo(), h.redo()); // Hi (empty) Hi

const PAIRS: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

function isBalanced(text: string): boolean {
  const stack = new Stack<string>();
  for (const ch of text) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else if (ch in PAIRS) {
      if (stack.pop() !== PAIRS[ch]) return false;
    }
  }
  return stack.isEmpty();
}

function evalRpn(tokens: string[]): number {
  const stack = new Stack<number>();
  for (const token of tokens) {
    if (["+", "-", "*", "/"].includes(token)) {
      const b = stack.pop()!; // the right operand comes off first
      const a = stack.pop()!;
      if (token === "+") stack.push(a + b);
      else if (token === "-") stack.push(a - b);
      else if (token === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!;
}

console.log(evalRpn(["3", "4", "+", "2", "*"])); // 14

function daysUntilWarmer(temps: number[]): number[] {
  const result = new Array<number>(temps.length).fill(0);
  const waiting = new Stack<number>(); // indexes, temps decreasing
  for (let i = 0; i < temps.length; i++) {
    while (!waiting.isEmpty() && temps[waiting.peek()!] < temps[i]) {
      const j = waiting.pop()!;
      result[j] = i - j;
    }
    waiting.push(i);
  }
  return result;
}

enqueue(a)  enqueue(b)  enqueue(c)  dequeue() -> a
front [a]   [a b]       [a b c]     [b c] front

import { LinkedList } from "./linked-list.ts";

class Queue<T> {
  private list = new LinkedList<T>();

  get size(): number {
    return this.list.size;
  }

  isEmpty(): boolean {
    return this.list.size === 0;
  }

  enqueue(value: T): void {
    this.list.append(value);
  }

  dequeue(): T | undefined {
    return this.list.removeFirst();
  }

  peek(): T | undefined {
    return this.list.head?.value;
  }
}

const q = new Queue<string>();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");

console.log(q.dequeue(), q.peek(), q.size); // a b 2

capacity 3, after pushing 1, 2, 3, then 4 and 5:

push 1,2,3:  [1, 2, 3]   start=0 count=3
push 4:      [4, 2, 3]   start=1 count=3   (overwrote 1)
push 5:      [4, 5, 3]   start=2 count=3   (overwrote 2)

Reading in order from start: 3, 4, 5

class CircularBuffer<T> {
  private items: (T | undefined)[];
  private start = 0;
  private count = 0;

  constructor(readonly capacity: number) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.items = new Array(capacity);
  }

  push(value: T): T | undefined {
    const end = (this.start + this.count) % this.capacity;
    if (this.count < this.capacity) {
      this.items[end] = value;
      this.count++;
      return undefined;
    }
    const dropped = this.items[this.start]; // full: replace the oldest
    this.items[this.start] = value;
    this.start = (this.start + 1) % this.capacity;
    return dropped;
  }

  shift(): T | undefined {
    if (this.count === 0) return undefined;
    const value = this.items[this.start];
    this.items[this.start] = undefined;
    this.start = (this.start + 1) % this.capacity;
    this.count--;
    return value;
  }
}

const b = new CircularBuffer<number>(3);
for (let i = 1; i <= 5; i++) b.push(i);

console.log(b.toArray().join(",")); // 3,4,5

enqueue 1, 2, 3 -> inbox (bottom to top): 1 2 3
dequeue: outbox is empty, so pour:
  pop 3 -> push to outbox, pop 2 -> push, pop 1 -> push
  outbox (bottom to top): 3 2 1   -> pop gives 1. Correct.

class TwoStackQueue<T> {
  private inbox = new Stack<T>();
  private outbox = new Stack<T>();

  enqueue(value: T): void {
    this.inbox.push(value);
  }

  dequeue(): T | undefined {
    if (this.outbox.isEmpty()) {
      while (!this.inbox.isEmpty()) this.outbox.push(this.inbox.pop()!);
    }
    return this.outbox.pop();
  }
}

export class Stack<T> {
  private items: T[] = [];

  get size(): number {
    return this.items.length;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  // O(1) amortized
  push(value: T): void {
    this.items.push(value);
  }

  // O(1)
  pop(): T | undefined {
    return this.items.pop();
  }

  // O(1)
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  toArray(): T[] {
    return [...this.items];
  }
}

const PAIRS: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

export function isBalanced(text: string): boolean {
  const stack = new Stack<string>();
  for (const ch of text) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else if (ch in PAIRS) {
      if (stack.pop() !== PAIRS[ch]) return false;
    }
  }
  return stack.isEmpty();
}

// Reverse Polish notation: "3 4 + 2 *" -> 14
export function evalRpn(tokens: string[]): number {
  const stack = new Stack<number>();
  for (const token of tokens) {
    if (["+", "-", "*", "/"].includes(token)) {
      const b = stack.pop()!;
      const a = stack.pop()!;
      if (token === "+") stack.push(a + b);
      else if (token === "-") stack.push(a - b);
      else if (token === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!;
}

// Monotonic stack: days until a warmer temperature
export function daysUntilWarmer(temps: number[]): number[] {
  const result = new Array<number>(temps.length).fill(0);
  const waiting = new Stack<number>(); // indexes, temps decreasing
  for (let i = 0; i < temps.length; i++) {
    while (!waiting.isEmpty() && temps[waiting.peek()!] < temps[i]) {
      const j = waiting.pop()!;
      result[j] = i - j;
    }
    waiting.push(i);
  }
  return result;
}

// Stack that also reports its minimum in O(1)
export class MinStack {
  private items: { value: number; min: number }[] = [];

  push(value: number): void {
    const min = this.items.length
      ? Math.min(value, this.items[this.items.length - 1].min)
      : value;
    this.items.push({ value, min });
  }

  pop(): number | undefined {
    return this.items.pop()?.value;
  }

  min(): number | undefined {
    return this.items[this.items.length - 1]?.min;
  }
}

// Undo / redo history
export class History<T> {
  private undoStack = new Stack<T>();
  private redoStack = new Stack<T>();

  constructor(private current: T) {}

  get value(): T {
    return this.current;
  }

  set(next: T): void {
    this.undoStack.push(this.current);
    this.current = next;
    this.redoStack = new Stack<T>(); // a new edit clears redo
  }

  undo(): T {
    if (!this.undoStack.isEmpty()) {
      this.redoStack.push(this.current);
      this.current = this.undoStack.pop()!;
    }
    return this.current;
  }

  redo(): T {
    if (!this.redoStack.isEmpty()) {
      this.undoStack.push(this.current);
      this.current = this.redoStack.pop()!;
    }
    return this.current;
  }
}

import { LinkedList } from "./linked-list.ts";
import { Stack } from "./stack.ts";

// Queue on top of the linked list: both ends are O(1).
export class Queue<T> {
  private list = new LinkedList<T>();

  get size(): number {
    return this.list.size;
  }

  isEmpty(): boolean {
    return this.list.size === 0;
  }

  enqueue(value: T): void {
    this.list.append(value);
  }

  dequeue(): T | undefined {
    return this.list.removeFirst();
  }

  peek(): T | undefined {
    return this.list.head?.value;
  }

  toArray(): T[] {
    return this.list.toArray();
  }
}

// Fixed-size ring: when full, the oldest item is overwritten.
export class CircularBuffer<T> {
  private items: (T | undefined)[];
  private start = 0;
  private count = 0;

  constructor(readonly capacity: number) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.items = new Array(capacity);
  }

  get size(): number {
    return this.count;
  }

  isFull(): boolean {
    return this.count === this.capacity;
  }

  // O(1). Returns the overwritten item, if any.
  push(value: T): T | undefined {
    const end = (this.start + this.count) % this.capacity;
    if (this.count < this.capacity) {
      this.items[end] = value;
      this.count++;
      return undefined;
    }
    const dropped = this.items[this.start];
    this.items[this.start] = value;
    this.start = (this.start + 1) % this.capacity;
    return dropped;
  }

  // O(1)
  shift(): T | undefined {
    if (this.count === 0) return undefined;
    const value = this.items[this.start];
    this.items[this.start] = undefined;
    this.start = (this.start + 1) % this.capacity;
    this.count--;
    return value;
  }

  toArray(): T[] {
    const out: T[] = [];
    for (let i = 0; i < this.count; i++) {
      out.push(this.items[(this.start + i) % this.capacity] as T);
    }
    return out;
  }
}

// Interview classic: a queue built from two stacks.
export class TwoStackQueue<T> {
  private inbox = new Stack<T>();
  private outbox = new Stack<T>();

  enqueue(value: T): void {
    this.inbox.push(value);
  }

  dequeue(): T | undefined {
    if (this.outbox.isEmpty()) {
      while (!this.inbox.isEmpty()) this.outbox.push(this.inbox.pop()!);
    }
    return this.outbox.pop();
  }

  get size(): number {
    return this.inbox.size + this.outbox.size;
  }
}

import { test } from "node:test";
import assert from "node:assert/strict";
import { Stack, isBalanced, evalRpn, daysUntilWarmer, MinStack, History } from "./stack.ts";

test("Stack is last in, first out", () => {
  const s = new Stack<number>();
  s.push(1);
  s.push(2);
  assert.equal(s.peek(), 2);
  assert.equal(s.pop(), 2);
  assert.equal(s.pop(), 1);
  assert.equal(s.pop(), undefined);
  assert.equal(s.isEmpty(), true);
});

test("isBalanced", () => {
  assert.equal(isBalanced("{[()]}"), true);
  assert.equal(isBalanced("a(b[c]d)e"), true);
  assert.equal(isBalanced("([)]"), false);
  assert.equal(isBalanced("(("), false);
  assert.equal(isBalanced(")"), false);
  assert.equal(isBalanced(""), true);
});

test("evalRpn", () => {
  assert.equal(evalRpn(["3", "4", "+", "2", "*"]), 14);
  assert.equal(evalRpn(["10", "2", "8", "*", "+", "3", "-"]), 23);
  assert.equal(evalRpn(["7", "2", "/"]), 3);
});

test("daysUntilWarmer", () => {
  assert.deepEqual(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0]);
});

test("MinStack", () => {
  const s = new MinStack();
  s.push(5);
  s.push(2);
  s.push(7);
  assert.equal(s.min(), 2);
  s.pop();
  s.pop();
  assert.equal(s.min(), 5);
});

test("History undo and redo", () => {
  const h = new History("a");
  h.set("ab");
  h.set("abc");
  assert.equal(h.undo(), "ab");
  assert.equal(h.undo(), "a");
  assert.equal(h.undo(), "a");
  assert.equal(h.redo(), "ab");
  h.set("abx");
  assert.equal(h.redo(), "abx");
});

import { test } from "node:test";
import assert from "node:assert/strict";
import { Queue, CircularBuffer, TwoStackQueue } from "./queue.ts";

test("Queue is first in, first out", () => {
  const q = new Queue<string>();
  q.enqueue("a");
  q.enqueue("b");
  assert.equal(q.peek(), "a");
  assert.equal(q.dequeue(), "a");
  assert.equal(q.dequeue(), "b");
  assert.equal(q.dequeue(), undefined);
  assert.equal(q.isEmpty(), true);
});

test("CircularBuffer overwrites the oldest", () => {
  const b = new CircularBuffer<number>(3);
  [1, 2, 3].forEach((n) => b.push(n));
  assert.equal(b.push(4), 1);
  assert.equal(b.push(5), 2);
  assert.deepEqual(b.toArray(), [3, 4, 5]);
  assert.equal(b.shift(), 3);
  assert.deepEqual(b.toArray(), [4, 5]);
  b.push(6);
  b.push(7);
  assert.deepEqual(b.toArray(), [5, 6, 7]);
});

test("TwoStackQueue keeps FIFO order", () => {
  const q = new TwoStackQueue<number>();
  q.enqueue(1);
  q.enqueue(2);
  assert.equal(q.dequeue(), 1);
  q.enqueue(3);
  assert.equal(q.dequeue(), 2);
  assert.equal(q.dequeue(), 3);
  assert.equal(q.dequeue(), undefined);
});

npx tsx --test

import { Stack, isBalanced, evalRpn, daysUntilWarmer, History } from "./src/stack";
import { Queue, CircularBuffer } from "./src/queue";

const s = new Stack<string>();
s.push("a");
s.push("b");
s.push("c");
console.log(s.peek(), s.pop(), s.size);
console.log(isBalanced("{[()]}"), isBalanced("([)]"), isBalanced("(("));
console.log(evalRpn(["3", "4", "+", "2", "*"]));
console.log(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]).join(" "));

const h = new History("");
h.set("Hi");
h.set("Hi there");
console.log(h.undo(), h.undo(), h.redo());

const q = new Queue<string>();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.dequeue(), q.peek(), q.size);

const ring = new CircularBuffer<number>(3);
for (let i = 1; i <= 5; i++) ring.push(i);
console.log(ring.toArray().join(","));

npx tsx demo.ts

c c 2
true false false
14
1 1 4 2 1 1 0 0
Hi  Hi
a b 2
3,4,5