JavaScript 배열로 구현하는 큐 (Queue)

들어가기 전에

자바스크립트는 큐(Queue) 자료구조를 제공 해 주지 않기 때문에 필요한 경우 직접 구현해서 사용해야 한다.

자바스크립트 배열 내장 메서드 push()와 shift()를 사용해서 큐 처럼 사용할 수는 있다. 하지만 shift()의 경우 시간 복잡도가 O(N)이기 때문에 실제로 큐를 사용하는 것 보다 느려지게 된다.

따라서 이번 포스팅에서는 자바스크립트 배열로 큐를 구현 해보려고 한다.

이 글은 Queue에 대한 개념은 다루지 않았습니다.

Queue에 대한 개념은 [자료구조] 큐(Queue)의 개념과 구현(C) & 용도에서 자세히 다루고 있으니, 개념이 아직 안잡히신 분들은 먼저 읽고 오시는 것을 추천드립니다.

JavaScript (선형)배열로 구현하는 큐 (Queue)

class Queue {
  constructor() {
      this.queue = [];
      this.front = 0;
      this.rear = 0;
  }

  enqueue(val) {
      this.queue[this.rear++] = val;
  }

  dequeue() {
      const val = this.queue[this.front++];
      return val;
  }

  getFirst() {
    return this.queue[this.front];
  }

  getMax() {
      return Math.max(...this.queue.slice(this.front));
  }

  size() {
      return this.rear - this.front;
  }

}

// queue 사용
const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5); // queue: [ 1, 2, 3, 4, 5 ], front: 0, rear: 5

queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue(); // queue: [ 1, 2, 3, 4, 5 ], front: 4, rear: 5

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3); // queue: [1, 2, 3, 4, 5, 1, 2, 3], front: 4, rear: 8

💡더 알아보기

위와 같은 방식으로 큐를 구현하면 한 가지 단점이 있다. dequeue()를 해도 해당 인덱스는 메모리가 잡힌 상태로 유지 되기 때문에 가비지 컬렉터가 수거 해 가기 전까지 메모리 누수가 발생한다.

이와 같은 방법을 해결하기 위해선 원형 배열로 큐를 구현해 주면 된다. 원형 배열로 구현한 큐는 조만간 update 하려고 한다.

References

• 자바스크립트 Array 메소드 및 예제에 대한 시간 복잡도 Big O