자바스크립트로 큐(Queue) 구현하기

Queue란?

"Oh, I'll put this in my watch later queue!"

플레이리스트 큐, 입장 대기 큐 등.. 우리가 직관적으로 아는 그 큐 맞다.

선입선출, 들어온 대로 나가는 리스트인 queue이다.

 

자바스크립트에서 배열과 shift메소드를 Queue 대용으로 쓰면 안 좋은 이유

자바스크립트 배열을 shift 메소드를 쓰며 queue같이 쓰는 것도 가능하긴 하지만

대규모 데이터를 queue로 처리해야될 때 자바스크립트 배열은 좋은 선택지가 아니다.

왜냐하면 shift()메소드로 특정 인덱스 인자를 제거했을 때,

다음 인덱스에 있는 인자를 해당 빈 인덱스에 끌어오고, 또 다다음것을 다음으로 끌어오고...

이런 O(n)시간복잡도의 재배치가 발생하기 때문이다. 얼마 안 되는 데이터면 shift로 처리하고 말지만,

십만개가 넘는 데이터를 shift()할때마다 위와 같은 재배치를 한다면 얼마나 느려질지 안 봐도 뻔하다.

 

그러므로 주로 자바스크립트로 코테를 한다면 Queue를 외울 수 밖에 없다.

이젠 막 외우려 하지 않아도 저절로 외워진달까..

bfs를 풀려면 필수적으로 알아야 하는 자료구조이기도 하다.

 

class Queue {
  constructor() {
    this.list = {};
    this.head = 0;
    this.tail = 0;
  }

  enqueue(item) {
    this.list[this.tail] = item;
    this.tail++;
  }

  dequeue() {
    if (this.head === this.tail) return null;
    let item = this.list[this.head];
    delete this.list[this.head];
    this.head++;
    return item;
  }

  getLength() {
    return this.tail - this.head;
  }

  peek() {
    return this.list[this.head];
  }
}