data-structures.ts

class Queue<T> {
  private items: { [key: number]: T } = {}
  private frontIndex: number = 0
  private backIndex: number = 0

  enqueue (item: T): void {
    this.items[this.backIndex] = item
    this.backIndex++
  }

  dequeue (): T | null {
    if (!this.isEmpty()) {
      const item = this.items[this.frontIndex]
      delete this.items[this.frontIndex]
      this.frontIndex++
      return item
    }
    return null
  }

  peek (): T | null {
    if (!this.isEmpty()) {
      return this.items[this.frontIndex]
    }
    return null
  }

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

  size (): number {
    return this.backIndex - this.frontIndex
  }

  clear (): void {
    this.items = {}
    this.frontIndex = 0
    this.backIndex = 0
  }
}

// const q = new Queue()
// console.log(
//   q.enqueue({ message: 'Hell world!' }),
//   q.dequeue(),
//   q.enqueue({ message: 'British Virgin Islands' }),
//   q.enqueue({ message: 'Marshall Islands' }),
//   q.enqueue({ message: 'St. Kitts & Nevis' }),
//   q.peek(),
//   q.size(),
//   q.isEmpty(),
// )

interface IStack<T = unknown> {
  push: (item: T) => void
  pop: () => T | null
  peek: () => T | null
  size: () => number
  isEmpty: () => boolean
  clear: () => void
}

class Stack<T> implements IStack<T> {
  private items: { [key: number]: T } = {}
  private top: number = 0

  push (item: T): void {
    this.items[this.top] = item
    this.top++
  }

  pop (): T | null {
    if (this.isEmpty()) {
      return null
    }
    this.top--
    const item = this.items[this.top]
    delete this.items[this.top]
    return item
  }

  peek (): T | null {
    if (this.isEmpty()) {
      return null
    }
    return this.items[this.top - 1]
  }

  size (): number {
    return this.top
  }

  isEmpty (): boolean {
    return this.top === 0
  }

  clear (): void {
    this.items = {}
    this.top = 0
  }
}

// const s = new Stack()
// s.push(100)
// s.push(200)
// s.push(300)
// s.push(500)
// console.log(
//   s.pop(),
//   s.peek(),
//   s.size(),
//   s.isEmpty()
// )

class MinStackPlugin<T> {
  private stack: Stack<T>
  private minStack: Stack<T>

  constructor(stackInstance: Stack<T>) {
    this.stack = stackInstance
    this.minStack = new Stack<T>()
  }

  push (element: T): void {
    this.stack.push(element)
    if (this.minStack.isEmpty() || element <= this.minStack.peek()!) {
      this.minStack.push(element)
    }
  }

  pop (): T | null {
    const element = this.stack.pop()
    if (element === this.minStack.peek()) {
      this.minStack.pop()
    }
    return element
  }

  peek (): T | null {
    return this.stack.peek()
  }

  isEmpty (): boolean {
    return this.stack.isEmpty()
  }

  size (): number {
    return this.stack.size()
  }

  clear (): void {
    this.stack.clear()
    this.minStack.clear()
  }

  getMin (): T | null {
    return this.minStack.peek()
  }
}

const stack = new Stack<number>()
const minStack = new MinStackPlugin<number>(stack)
// minStack.push(10);
// minStack.push(20);
// minStack.push(5);
// minStack.push(15);
// console.log(minStack.getMin()); // 5
// minStack.pop();
// console.log(minStack.getMin()); // 5
// minStack.pop();
// console.log(minStack.getMin()); // 10
// minStack.pop();
// console.log(minStack.getMin()); // 10
// minStack.clear();
// console.log(minStack.isEmpty()); // true


class TreeNode<T> {
  public value: T
  public left: TreeNode<T> | null
  public right: TreeNode<T> | null
  public height: number
  constructor(value: T) {
    this.value = value
    this.left = null
    this.right = null
    this.height = 1
  }
}


class AVLTree<T> {
  private root: TreeNode<T> | null = null

  private getHeight (node: TreeNode<T> | null): number {
    return node ? node.height : 0
  }

  private updateHeight (node: TreeNode<T>): void {
    node.height = Math.max(
      this.getHeight(node.left),
      this.getHeight(node.right)
    )
  }

  private getBalanceFactor (node: TreeNode<T>): number {
    return node
      ? this.getHeight(node.left) - this.getHeight(node.right)
      : 0
  }

  private rotateRight (y: TreeNode<T>): TreeNode<T> {
    const x = y.left!
    const aux = x.right

    x.right = y
    y.left = aux

    this.updateHeight(y)
    this.updateHeight(x)

    return x
  }

  // etc
}