avatar
Published on

자바스크립트 자료 구조

Author
  • avatar
    Name
    yceffort

Table of Contents

Stack

  • push와 pop으로 구성된 stack
  • LIFO
export default class Stack<T> {
  private stack: T[]

  constructor() {
    this.stack = []
  }

  push(value: T) {
    this.stack.push(value)
  }

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

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

Queue

  • 데이터 삽입과 삭제가 서로 반대쪽에서 일어나는 자료구조
  • FIFO
export default class Queue<T> {
  private queue: T[]

  constructor() {
    this.queue = []
  }

  dequeue(): T | undefined {
    return this.queue.shift()
  }

  enqueue(value: T) {
    this.queue.push(value)
    return this
  }

  size() {
    return this.queue.length
  }
}

우선순위 큐

  • 각 원소들이 우선순위를 가지고 있는 큐
  • 큐에서 무작정 pop이나 shift하는 것이 아니라, 우선순위가 가장 높은 것이 나오는 형태
export type PQItem<T> = { priority: number; data: T }

export default class PriorityQueue<T> {
  private queue: PQItem<T>[]

  constructor() {
    this.queue = []
  }

  enqueue(value: PQItem<T>) {
    this.queue.push(value)
  }

  dequeue(): PQItem<T> | undefined {
    let entry = 0

    this.queue.forEach((_, i) => {
      const nextIndex = i + 1

      if (!this.queue[nextIndex]) {
        return undefined
      }

      if (this.queue[entry].priority > this.queue[nextIndex].priority) {
        entry = nextIndex
      }
    })

    const [dequeuedItem] = this.queue.splice(entry, 1)

    return dequeuedItem
  }
}

연결 리스트

export class Node<T> {
  data: T
  next: Node<T> | null

  constructor(data: T) {
    this.data = data
    this.next = null
  }
}

export default class LinkedList<T> {
  // TODO

해쉬테이블

이진 트리

Issue on GitHub