[JS] 자바스크립트에는 내장 라이브러리에 큐가 없는데 어떡하지

BFS 문제를 풀다가 JS에는 큐가 구현되어 있지 않다는 것을 알게 되었다 ^__^

코딩테스트에서 큐가 필요한 상황이 오면 어떻게 해야 할까?

 

 

1. 시간복잡도 O(N)

시간제한이 널널할 때는 Array.shift() 를 사용하자.

• 큐의 pop과 동일한 기능을 한다.
• 하지만 배열의 원소를 하나씩 당기기 때문에 시간복잡도가 O(N)이다.

 

 

2. 시간복잡도 O(1)

• pop할 원소의 인덱스를 변수를 만들어 저장하자.

  let front = 0;
  while (front < queue.length) {
    const [x, y, z] = queue[top];
    front += 1;

  /* ... */

  }

• 인덱스를 옮김으로써 가장 앞의 원소가 어떤 것인지 판별할 수 있게 되었다.
• 실제 원소가 삭제되지는 않지만 FIFO 흉내내기가 가능하다.

 

 

3. 직접 구현

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  enqueue(data) {
    const newItem = new Node(data);

    if (!this.length) {
      this.front = newItem;
    } else {
      this.rear.next = newItem;
    }

    this.rear = newItem;

    this.length++;
  }

  dequeue() {
    if (!this.length) {
      return null;
    }

    if (this.front === this.rear) {
      this.rear = null;
    }
    const popItem = this.front.data;
    this.front = this.front.next;

    this.length--;

    return popItem;
  }
}