Stacks & Queues: Cấu Trúc Dữ Liệu LIFO và FIFO

// TypeScript - Stack dùng Array
class Stack<T> {
  private items: T[] = [];
 
  push(item: T): void {
    this.items.push(item);
  }
 
  pop(): T | undefined {
    if (this.isEmpty()) throw new Error("Stack rỗng");
    return this.items.pop();
  }
 
  peek(): T {
    if (this.isEmpty()) throw new Error("Stack rỗng");
    return this.items[this.items.length - 1];
  }
 
  isEmpty(): boolean {
    return this.items.length === 0;
  }
 
  size(): number {
    return this.items.length;
  }
 
  toString(): string {
    return `[${this.items.join(", ")}] <- đỉnh`;
  }
}
 
// Sử dụng
const stack = new Stack<number>();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.toString()); // [10, 20, 30] <- đỉnh
console.log(stack.peek());     // 30
console.log(stack.pop());      // 30
console.log(stack.size());     // 2

# Python - Stack dùng List
class Stack:
    def __init__(self):
        self.items = []
 
    def push(self, item):
        self.items.append(item)
 
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack rỗng")
        return self.items.pop()
 
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack rỗng")
        return self.items[-1]
 
    def is_empty(self):
        return len(self.items) == 0
 
    def size(self):
        return len(self.items)
 
    def __repr__(self):
        return f"{self.items} <- đỉnh"
 
# Sử dụng
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack)         # [10, 20, 30] <- đỉnh
print(stack.peek())  # 30
print(stack.pop())   # 30
print(stack.size())  # 2

// TypeScript - Stack dùng Linked List
class ListNode<T> {
  val: T;
  next: ListNode<T> | null;
  constructor(val: T) {
    this.val = val;
    this.next = null;
  }
}
 
class LinkedStack<T> {
  private head: ListNode<T> | null = null;
  private _size = 0;
 
  push(item: T): void {
    const node = new ListNode(item);
    node.next = this.head;
    this.head = node;
    this._size++;
  }
 
  pop(): T {
    if (!this.head) throw new Error("Stack rỗng");
    const val = this.head.val;
    this.head = this.head.next;
    this._size--;
    return val;
  }
 
  peek(): T {
    if (!this.head) throw new Error("Stack rỗng");
    return this.head.val;
  }
 
  isEmpty(): boolean {
    return this.head === null;
  }
 
  size(): number {
    return this._size;
  }
}

// TypeScript - Queue Naïve (O(n) dequeue — tránh trong phỏng vấn)
class NaiveQueue<T> {
  private items: T[] = [];
 
  enqueue(item: T): void {
    this.items.push(item); // O(1) amortized
  }
 
  dequeue(): T | undefined {
    return this.items.shift(); // ⚠️ O(n) — dịch chuyển tất cả phần tử
  }
}

// TypeScript - Queue dùng Linked List (O(1) cho tất cả thao tác)
class QueueNode<T> {
  val: T;
  next: QueueNode<T> | null = null;
  constructor(val: T) { this.val = val; }
}
 
class Queue<T> {
  private head: QueueNode<T> | null = null; // đầu
  private tail: QueueNode<T> | null = null; // cuối
  private _size = 0;
 
  enqueue(item: T): void {
    const node = new QueueNode(item);
    if (!this.tail) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this._size++;
  }
 
  dequeue(): T {
    if (!this.head) throw new Error("Queue rỗng");
    const val = this.head.val;
    this.head = this.head.next;
    if (!this.head) this.tail = null; // queue trở nên rỗng
    this._size--;
    return val;
  }
 
  front(): T {
    if (!this.head) throw new Error("Queue rỗng");
    return this.head.val;
  }
 
  isEmpty(): boolean {
    return this.head === null;
  }
 
  size(): number {
    return this._size;
  }
}
 
// Sử dụng
const q = new Queue<number>();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log(q.front());    // 10
console.log(q.dequeue());  // 10
console.log(q.front());    // 20
console.log(q.size());     // 2

# Python - Queue dùng collections.deque (O(1) cho tất cả thao tác)
from collections import deque
 
class Queue:
    def __init__(self):
        self.items = deque()
 
    def enqueue(self, item):
        self.items.append(item)       # Thêm vào phải (cuối)
 
    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue rỗng")
        return self.items.popleft()   # Xóa từ trái (đầu) — O(1)
 
    def front(self):
        if self.is_empty():
            raise IndexError("Queue rỗng")
        return self.items[0]
 
    def is_empty(self):
        return len(self.items) == 0
 
    def size(self):
        return len(self.items)
 
# Sử dụng
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.front())    # 10
print(q.dequeue())  # 10
print(q.front())    # 20

// TypeScript - Circular Queue (ring buffer)
class CircularQueue<T> {
  private items: (T | null)[];
  private head = 0;
  private tail = 0;
  private _size = 0;
  private capacity: number;
 
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity).fill(null);
  }
 
  enqueue(item: T): boolean {
    if (this._size === this.capacity) return false; // đầy
    this.items[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;   // wrap around
    this._size++;
    return true;
  }
 
  dequeue(): T | null {
    if (this._size === 0) return null; // rỗng
    const val = this.items[this.head] as T;
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.capacity;   // wrap around
    this._size--;
    return val;
  }
 
  isFull(): boolean {
    return this._size === this.capacity;
  }
 
  isEmpty(): boolean {
    return this._size === 0;
  }
}

// TypeScript - Deque dùng Doubly Linked List
class DequeNode<T> {
  val: T;
  prev: DequeNode<T> | null = null;
  next: DequeNode<T> | null = null;
  constructor(val: T) { this.val = val; }
}
 
class Deque<T> {
  private head: DequeNode<T> | null = null;
  private tail: DequeNode<T> | null = null;
  private _size = 0;
 
  addFront(item: T): void {
    const node = new DequeNode(item);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this._size++;
  }
 
  addRear(item: T): void {
    const node = new DequeNode(item);
    if (!this.tail) {
      this.head = this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this._size++;
  }
 
  removeFront(): T {
    if (!this.head) throw new Error("Deque rỗng");
    const val = this.head.val;
    this.head = this.head.next;
    if (this.head) this.head.prev = null;
    else this.tail = null;
    this._size--;
    return val;
  }
 
  removeRear(): T {
    if (!this.tail) throw new Error("Deque rỗng");
    const val = this.tail.val;
    this.tail = this.tail.prev;
    if (this.tail) this.tail.next = null;
    else this.head = null;
    this._size--;
    return val;
  }
 
  peekFront(): T {
    if (!this.head) throw new Error("Deque rỗng");
    return this.head.val;
  }
 
  peekRear(): T {
    if (!this.tail) throw new Error("Deque rỗng");
    return this.tail.val;
  }
 
  isEmpty(): boolean { return this._size === 0; }
  size(): number { return this._size; }
}

# Python - Deque dùng collections.deque
from collections import deque
 
dq = deque()
dq.appendleft(10)  # addFront
dq.append(20)      # addRear
dq.appendleft(5)   # addFront
print(list(dq))    # [5, 10, 20]
dq.popleft()       # removeFront -> 5
dq.pop()           # removeRear  -> 20
print(list(dq))    # [10]

// TypeScript
function isValid(s: string): boolean {
  const stack: string[] = [];
  const matching: Record<string, string> = {
    ')': '(',
    '}': '{',
    ']': '[',
  };
 
  for (const char of s) {
    if ('({['.includes(char)) {
      stack.push(char);           // Push ngoặc mở
    } else {
      // Ngoặc đóng: phải khớp với đỉnh stack
      if (stack.length === 0 || stack[stack.length - 1] !== matching[char]) {
        return false;
      }
      stack.pop();
    }
  }
 
  return stack.length === 0;      // Stack phải rỗng ở cuối
}
 
// Ví dụ
console.log(isValid("()"));       // true
console.log(isValid("()[]{}"));   // true
console.log(isValid("(]"));       // false
console.log(isValid("([)]"));     // false
console.log(isValid("{[]}"));     // true

# Python
def is_valid(s: str) -> bool:
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
 
    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
 
    return len(stack) == 0
 
# Ví dụ
print(is_valid("()"))       # True
print(is_valid("()[]{}"))   # True
print(is_valid("(]"))       # False

char='(' → push → stack=['(']
char='[' → push → stack=['(', '[']
char=')' → matching[')']='(' nhưng top='[' → KHÔNG KHỚP → return false

// TypeScript
function evalRPN(tokens: string[]): number {
  const stack: number[] = [];
  const ops = new Set(['+', '-', '*', '/']);
 
  for (const token of tokens) {
    if (ops.has(token)) {
      const b = stack.pop()!;  // Toán hạng thứ hai
      const a = stack.pop()!;  // Toán hạng thứ nhất
      let result: number;
      if (token === '+') result = a + b;
      else if (token === '-') result = a - b;
      else if (token === '*') result = a * b;
      else result = Math.trunc(a / b); // Cắt về phía không
      stack.push(result);
    } else {
      stack.push(parseInt(token));
    }
  }
 
  return stack[0];
}
 
console.log(evalRPN(["2","1","+","3","*"]));     // 9
console.log(evalRPN(["4","13","5","/","+"]));    // 6

# Python
def eval_rpn(tokens: list[str]) -> int:
    stack = []
    ops = {'+', '-', '*', '/'}
 
    for token in tokens:
        if token in ops:
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))  # Cắt về phía không
        else:
            stack.append(int(token))
 
    return stack[0]

// TypeScript - Monotonic Stack
function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack: number[] = []; // lưu chỉ số
 
  for (let i = 0; i < n; i++) {
    // Khi nhiệt độ hiện tại ấm hơn nhiệt độ ở đỉnh stack
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop()!;
      result[idx] = i - idx; // số ngày đến khi ấm hơn
    }
    stack.push(i);
  }
 
  return result;
}
 
console.log(dailyTemperatures([73,74,75,71,69,72,76,73]));
// [1, 1, 4, 2, 1, 1, 0, 0]

# Python
def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # lưu chỉ số
 
    for i, temp in enumerate(temperatures):
        while stack and temp > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)
 
    return result

i=0, temp=73 → stack=[] → push 0 → stack=[0]
i=1, temp=74 → 74>73(idx=0) → result[0]=1-0=1, stack=[] → push 1 → stack=[1]
i=2, temp=75 → 75>74(idx=1) → result[1]=2-1=1, stack=[] → push 2 → stack=[2]
i=3, temp=71 → 71<75 → push 3 → stack=[2,3]
i=4, temp=69 → 69<71 → push 4 → stack=[2,3,4]
i=5, temp=72 → 72>69(idx=4)→result[4]=1, 72>71(idx=3)→result[3]=2, 72<75 → push 5 → stack=[2,5]
i=6, temp=76 → 76>72(idx=5)→result[5]=1, 76>75(idx=2)→result[2]=4, stack=[] → push 6 → stack=[6]
i=7, temp=73 → 73<76 → push 7 → stack=[6,7]
Kết quả: result = [1,1,4,2,1,1,0,0]

// TypeScript
class MyQueue {
  private inbox: number[] = [];   // cho push
  private outbox: number[] = [];  // cho pop/peek
 
  push(x: number): void {
    this.inbox.push(x);
  }
 
  pop(): number {
    this.transfer();
    return this.outbox.pop()!;
  }
 
  peek(): number {
    this.transfer();
    return this.outbox[this.outbox.length - 1];
  }
 
  empty(): boolean {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }
 
  private transfer(): void {
    // Chỉ chuyển khi outbox rỗng (lazy)
    if (this.outbox.length === 0) {
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop()!);
      }
    }
  }
}
 
// Sử dụng
const queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.peek()); // 1 (FIFO: push đầu tiên)
console.log(queue.pop());  // 1
console.log(queue.pop());  // 2

# Python
class MyQueue:
    def __init__(self):
        self.inbox = []   # cho push
        self.outbox = []  # cho pop/peek
 
    def push(self, x: int) -> None:
        self.inbox.append(x)
 
    def pop(self) -> int:
        self._transfer()
        return self.outbox.pop()
 
    def peek(self) -> int:
        self._transfer()
        return self.outbox[-1]
 
    def empty(self) -> bool:
        return not self.inbox and not self.outbox
 
    def _transfer(self) -> None:
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

// TypeScript - Monotonic Deque
function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // lưu chỉ số, đầu = max
 
  for (let i = 0; i < nums.length; i++) {
    // Xóa các chỉ số ngoài cửa sổ hiện tại
    while (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }
 
    // Xóa các phần tử nhỏ hơn từ cuối (không thể là max)
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
 
    deque.push(i);
 
    // Bắt đầu ghi kết quả khi cửa sổ đầu tiên hoàn chỉnh
    if (i >= k - 1) {
      result.push(nums[deque[0]]); // đầu luôn là max
    }
  }
 
  return result;
}
 
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// [3, 3, 5, 5, 6, 7]

# Python
from collections import deque
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result = []
    dq = deque()  # lưu chỉ số
 
    for i, num in enumerate(nums):
        # Xóa chỉ số ngoài cửa sổ từ đầu
        while dq and dq[0] < i - k + 1:
            dq.popleft()
 
        # Xóa phần tử nhỏ hơn từ cuối
        while dq and nums[dq[-1]] < num:
            dq.pop()
 
        dq.append(i)
 
        if i >= k - 1:
            result.append(nums[dq[0]])
 
    return result

i=0, num=1  → deque=[0]
i=1, num=3  → 3>1 xóa 0, deque=[1]
i=2, num=-1 → deque=[1,2], cửa sổ=[1,3,-1] → result=[nums[1]]=3
i=3, num=-3 → deque=[1,2,3], cửa sổ=[3,-1,-3] → result=[3,3]
i=4, num=5  → 5>-3 xóa 3, 5>-1 xóa 2, 5>3 xóa 1, deque=[4] → result=[3,3,5]
i=5, num=3  → deque=[4,5] → result=[3,3,5,nums[4]]=5
i=6, num=6  → 6>3 xóa 5, 6>5 xóa 4, deque=[6] → result=[3,3,5,5,6]
i=7, num=7  → 7>6 xóa 6, deque=[7] → result=[3,3,5,5,6,7]

// TypeScript
class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];
 
  push(val: number): void {
    this.stack.push(val);
    const currentMin = this.minStack.length === 0
      ? val
      : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(currentMin);
  }
 
  pop(): void {
    this.stack.pop();
    this.minStack.pop();
  }
 
  top(): number {
    return this.stack[this.stack.length - 1];
  }
 
  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}
 
// Sử dụng
const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.getMin()); // -3
minStack.pop();
console.log(minStack.top());    // 0
console.log(minStack.getMin()); // -2

# Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        current_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(current_min)
 
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def get_min(self) -> int:
        return self.min_stack[-1]

// TypeScript - Monotonic Stack
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  // Xây dựng map next-greater cho nums2
  const nextGreater = new Map<number, number>();
  const stack: number[] = [];
 
  for (const num of nums2) {
    while (stack.length > 0 && stack[stack.length - 1] < num) {
      nextGreater.set(stack.pop()!, num);
    }
    stack.push(num);
  }
  // Các phần tử còn lại trong stack không có next greater → -1 (mặc định Map)
 
  return nums1.map(n => nextGreater.get(n) ?? -1);
}
 
console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1,3,-1]
console.log(nextGreaterElement([2,4], [1,2,3,4]));   // [3,-1]

# Python
def next_greater_element(nums1: list[int], nums2: list[int]) -> list[int]:
    next_greater = {}
    stack = []
 
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)
 
    return [next_greater.get(n, -1) for n in nums1]