Hyunjung Im


Stack

  • 좀 더 압축적인 데이터 구조
  • 후입 선출 LIFO
  • 연결 리스트를 사용할 수도 있다.
  • Call Stack
  • Undo/Redo
  • 브라우저 방문 기록
  • push, pop 상수시간

Big O of Stacks

InsertionO(1)
RemovalO(1)
SearchingO(N)
AccessO(N)

연결리스트로 stack 만들어보기

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

class Stack {
  constructor() {
    this.first = null
    this.last = null
    this.size = 0
  }

  push(val) {
    const newNode = new Node(val)

    this.size++

    if (!this.first) {
      this.first = newNode
      this.last = newNode
    } else {
      const temp = this.first
      this.first = newNode
      this.first.next = temp
    }

    return ++this.size
  }

  pop() {
    if (!this.first) {
      return null
    }

    if (!this.size) {
      this.last = null
    }

    const temp = this.first

    this.first = this.first.next
    this.size--

    return temp.value
  }
}
  • 연결 리스트로 만들 때는 shift를 이용해서 상수 시간이 되도록 만들기

Queue

  • 추가, 제거 이게 다임
  • FIFO, 선입선출, 들어간 순서대로 나온다.
  • 배열을 사용하면 간단하게 만들 수 있지만 성능을 신경써야 하는 경우라면 직접 큐 클래스를 만드는 것이 좋다.

Big O of Queues

InsertionO(1)
RemovalO(1)
SearchingO(N)
AccessO(N)
  • 일반적으로 enqueue, dequeue만 쓴다.

class로 queue 만들어보기

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

class Queue {
  constructor() {
    this.first = null
    this.last = null
    this.size = 0
  }

  enqueue(value) {
    const newNode = new Node(value)

    if (!this.size) {
      this.first = newNode
      this.last = newNode
    } else {
      this.last.next = newNode
      this.last = newNode
    }

    return ++this.size
  }

  dequeue() {
    if (!this.size) return null

    if (this.size === 1) {
      this.last = null
    }

    const temp = this.first
    this.first = this.first.next
    this.size--

    return temp.value
  }
}
  • 앞에 추가하고, tail을 삭제하면 삭제할 때 모든 노드르 순회해야 함으로 이점이 없으므로 앞에서 삭제하고 tail에 추가하는 식으로.