[자료구조] 선형 큐에 대한 코드 오류와 이해 with. JS

JS 알고리즘 공부 5회차 with. BaaaaaaaarkingDog

위 글에서 큐에 대한 설명과 간단한 코드를 작성했지만 이번엔 클래스를 이용해 만들어보겠습니다.

 

자료 구조에 대해서는 틈나면 코딩 테스트와 함께 공부해보려고 하고 있습니다. 이번 시간에는 위 글보다 더 오래전에 공부했던 내용에 대한 오류를 다시 살펴보고 새롭게 이해한 코드를 작성해 보겠습니다.

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

  size() {
    // 현재 큐의 크기 반환. isEmpty() 대체 가능
    // 오류가 발생하는 부분
    return this.rear === this.front ? 0 : this.rear - this.front + 1;
  }

  peek() {
    // 맨 앞의 노드 값 보여주기
    return q[this.front];
  }

  enqueue(item) {
    // 새로운 노드 삽입하기
    if (this.rear === this.front) {
      this.q[this.front] = item;
    } else {
      this.q[this.rear + 1] = item; // 오류가 발생하는 부분
    }
    this.rear += 1;
  }

  dequeue() {
    // 첫 노드 삭제하고 값 반환하기
    if (this.rear === this.front) {
      console.log("빈 큐입니다");
      return;
    } else if (this.rear < this.front) {
      console.log("에러 입니다. front 값이 더 클 수 없습니다.");
      return;
    }
    const temp = this.q[this.front];
    delete this.q[this.front];
    this.front += 1;
    return temp;
  }
}

 

위 큐는 enqueue 기능을 동작하면 오류가 발생합니다. 큐가 비어있다면 front에 넣고 아니라면 rear+1에 넣고 rear 값을 1 증가시킵니다. 이때 rear + 1에 넣게 되면 한 칸을 비우고 값을 채우게 됩니다. 물론 객체이기 때문에 값은 문제없이 들어갑니다. 하지만 한 칸을 비우고 값을 채우게 되면 크기를 구하는 size() 함수에서 문제가 발생합니다.

 

 

간단하게 enqueue와 dequeue를 실행해 보면 다음과 같이 2에 값이 저장되지 않고 3에 값이 저장되는 것을 볼 수 있습니다. 이 경우 현재 큐의 크기는 2이지만 size() 함수의 결과는 3으로 나오는 오류가 발생합니다.

 

덕분에 아주 고생을 했습니다... 과거에 분명히 코드를 실행해 봤을 거라고 생각했는데 앞으로는 과거의 나를 믿지 않고 한 번 더 확인할 필요가 있습니다.

 

다시 문제를 살펴보면 rear + 1에 넣는 게 문제이기 때문에 rear로 수정하면 바로 해결됩니다.

enqueue(item) {
  if (this.front == this.rear) {
    this.q[this.front] = item;
  } else {
    this.q[this.rear] = item;
  }
  this.rear += 1;
}

 

오류를 해결하는 과정에서 더 큐를 깔끔하게 만들 수 있는 방법을 알았기 때문에 새로 학습한 큐를 만들어 보겠습니다.

class QUEUE {
  constructor() {
    this.q = {};
    this.front = 0;
    this.rear = 0; // rear는 항상 다음 아이템이 들어올 장소를 가리킴
  }

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

  enqueue(item) {
    this.q[this.rear++] = item;
  }

  dequeue() {
    if (this.size() == 0) {
      return null;
    }
    const data = this.q[this.front];

    delete this.q[this.front++];

    return data;
  }
}

 

훨씬 코드가 간결해진 것을 확인할 수 있습니다. 여기서 중요한 것은 rear가 다음 아이템이 들어올 장소를 가리킨다는 것을 이해하는 것입니다.

 

하지만 객체를 사용해서 큐를 만들면 메모리가 많이 사용될 가능성이 있습니다. 그렇기 때문에 크기를 정해둔 선형 큐도 알아가도록 하겠습니다.

class CIRCULARQUEUE {
  constructor(capacity) {
    this.q = new Array(capacity);
    this.capacity = capacity; // 큐의 지정된 크기를 나타냅니다.
    this.front = 0;
    this.rear = 0;
    this.size = 0; // 순환 큐는 front와 rear로 크기를 구하기 귀찮아 따로 필드를 생성
  }
  
  isFull() { // 큐가 지정된 크기를 가득 채웠는지 확인
    return this.size === this.capacity;
  }
  
  isEmpty() {
    return this.size === 0;
  }
  
  peek() { // 첫 번째 요소 반환
    if(this.isEmpty()) {
      return null;
    }
    
    return this.q[this.front];
  }
  
  enqueue(item) {
    if(this.isFull()) { // 지정된 큐의 크기가 있기 때문에 검사하는 조건문
      // 에러를 반환 받을 수 없는 코테의 경우 다른 값을 return
      throw new Error('queue is full');
    }
    
    this.q[this.rear] = item;
    this.rear = (this.rear + 1) % this.capacity; // 순환 큐 rear 계산
    this.size++;
  }
  
  dequeue() {
    if(this.isEmpty()) {
      return null;
    }
    
    const temp = this.q[this.front];
    this.front = (this.front + 1) % this.capacity; // 순환 큐 front 계산
    
    this.size--;
    
    return temp;
  }
}

 

크기가 지정되어 있다면 선형 큐를 사용하는 게 메모리나 시간적인 측면에서 향상된 결과를 얻을 수 있습니다.