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

2021년 06월 30일

일반적인 큐에서의 문제점

자바스크립트 외에 다른 언어에서는 배열의 크기가 정해져 있기 때문에, 큐가 다 차면 데이터를 추가할 수가 없다.

또한, dequeue를 한 후 데이터를 전부 앞으로 당기면(배열의 인덱스를 재배치) 메모리적으로 매우 비효율적이다.

(자바스크립트는 배열로 큐를 구현한다 할때 인덱스가 0인 데이터를 제거하면 그 다음 데이터의 인덱스가 0으로 되기 때문에 문제가 되지 않음)

이 문제를 해결하기 위해 원형 큐를 사용

rear === front의 경우 큐가 비어있는건지 꽉 차있는건지 구분할 수가 없으므로 배열의 한 칸을 비워둔다.

rear + 1 === front 로 큐가 꽉 차있는지 알 수 있게 됨

enqueue할때 rear = rear +1을 하지 않고 나머지 연산자(%)를 사용하는 이유는 큐의 사이즈를 나머지로 연산함으로써 원형으로 돌게 해줌. dequeue도 마찬가지

function CircularQueue(size) {
  let items = [];
  let front = 0;
  let rear = 0;

  this.isEmpty = function () {
    return rear === front;
  };

  this.isFull = function () {
    return (rear + 1) % size === front;
  };

  this.enqueue = function (element) {
    if (this.isFull()) console.log("Memory is full!");
    else {
      items[(rear = (rear + 1) % size)] = element;
    }
  };
  this.dequeue = function () {
    if (this.isEmpty()) console.log("Queue is empty!");
    else {
      front = (front + 1) % size;
      return items[front];
    }
  };
  this.print = function () {
    if (this.isEmpty()) {
      console.log("Queue is empty!");
      return;
    }
    let string = "";
    let i = front;
    do {
      i = (i + 1) % size;
      string += items[i] + " ";
      if (i === rear) {
        console.log(string);
        break;
      }
    } while (i !== front);
  };
}