[자료구조] 큐(Queue)

큐(Queue)

큐는 가장 먼저 넣은 데이터가 가장 먼저 나오는 FIFO(First-in, First-out) 구조로, 스택과 반대되는 개념이다.

자료의 한 쪽 끝에서 삽입, 삭제가 같이 일어나는 스택과는 달리
큐는 자료의 한 쪽 끝에서 자료가 삽입되고, 그 반대쪽 끝에서 자료가 삭제되는 구조이다.

큐에서 핵심이 되는 포인터가 2개 있는데, 바로 front와 rear이다.
큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부르며, 접근은 가장 첫 원소와 끝 원소로만 가능하다.

다른 언어의 경우는 보통 내장 라이브러리에서 큐를 제공한다.
대표적으로 Java의 경우, java.util.Queue를 임포트하여 사용할 수 있고
Python의 경우, collections에서 deque를 임포트해서 큐처럼 사용할 수 있다.
하지만 자바스크립트는 큐와 관련된 객체가 내장되어 있지 않으므로, 직접 자료구조를 작성해야 한다.

여기서는 클래스를 이용해서 Queue를 구현해보자.

Queue 초기화

constructor 메서드를 통해 초기 큐의 구조와 값을 선언할 수 있다.
앞서 객체(Object)에 값을 저장하고, 두 개의 포인터 front와 rear를 사용하기로 했다면 이들에 대한 값을 초기화 해주어야 한다.

class Queue {
	constructor() {
    	this.storage = {};	// 값을 저장할 객체
      	this.front = 0;		// 첫 원소를 가리킬 포인터
      	this.rear = 0;		// 마지막 원소를 가리킬 포인터
    }
}

Size 구하기

큐에 담을 데이터로 객체를 사용하는 경우, 배열처럼 단순히 arr.length를 통해서는 값을 구하기 어렵다.
물론 객체를 배열로 바꾸는 객체 메서드 Object.keys / values / entries() 등을 이용하여 값을 변환 후,
length 프로퍼티를 통해 크기를 구할 수도 있지만 배열로 변환하는 과정은 O(N)의 시간복잡도가 소요된다.
따라서 배열로 변환하는 것보다는 투 포인터를 사용해서 이보다 더 빠르게 큐의 크기를 구할 수 있다.

큐에서 데이터를 하나씩 계속해서 추출하다보면 front와 rear가 가리키는 지점이 같아지는 순간이 오게 되는데,
이 때는 큐에 존재하는 데이터가 딱 1개인 경우를 말한다.
여기서 한 번 더 큐의 원소를 가져오면, 남아있는 데이터가 아무 것도 없는 상황이 만들어진다.

class Queue {
					...
	size() {
        // rear가 가리키는 값이 없을 때, 데이터가 아무것도 없는 경우
    	if (this.storage[rear] === undefined) {
        	return 0;
        } else {
        	return this.rear - this.front + 1;
        }    
    }
}

isEmpty

큐에서 데이터를 뽑아낼 때 큐가 비어있다면 오류가 발생할 수 있다.
따라서 큐가 비어있는지 확인하는 함수인 isEmpty()가 필요하다.
front와 rear 포인터가 동일하다면 그 사이에 요소가 없기 때문에 대기열이 비어 있음을 의미한다.

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

큐의 데이터 삽입, enQueue

큐에 데이터가 삽입되는 경우, rear 포인터의 위치만 조정된다.
데이터가 하나씩 들어올 때마다 rear 포인터는 이전 위치 + 1이 되고, 해당 위치에 들어온 데이터를 저장한다.

단, 이 때 데이터가 전혀 없는 경우를 주의해야 한다.

데이터가 아무 것도 없는 경우
1. 큐를 처음 초기화 했을 경우 (= 두 포인터 모두 0일 때)
2. 위에서처럼 중간에 데이터를 모두 꺼내는 경우 (= front + 1 === rear를 만족하는 경우)

분기가 나뉘는 처리는 좋은 방법이 아니기 때문에 이를 하나의 경우로 통합해서 처리해주는 것이 좋다. 따라서 2번째 경우는 고려하지 않는다. 즉 데이터가 아무 것도 없는 경우, 두 포인터가 모두 0을 바라보도록 재조정 해준다.

큐에 데이터가 존재하지 않는 경우, 0번 위치에 데이터를 삽입한다. 이 때, front와 rear의 위치는 아무런 변화가 없다. 데이터가 아무 것도 없을 때는 0번 위치에 데이터가 들어가게 되고 1개의 데이터만 있는 경우이기 때문에 front와 rear의 위치값은 동일하며 이는 곧 0번이기 때문이다.

class Queue {
					...  
  enQueue(value) {
      if (this.size() === 0) {	 // Queue에 데이터가 아무것도 없는 경우
          this.storage['0'] = value;
      } else {
          this.rear += 1;	 // rear의 위치를 1만큼 늘리고 해당 위치에 값 삽입
          this.storage[this.rear] = value;
      }
  }

큐의 데이터 반환, deQueue

데이터를 꺼내는 경우, front의 위치가 재조정될 것이다. 위치를 재조정하기 전에 기존 위치에 담긴 값을 제거해주는 과정이 반드시 필요하다.

그리고 큐에 데이터가 존재하지 않게 되는 시점을 고려해주어야 한다. 해당 시점은 큐에 데이터가 딱 1개만 존재하고 있을 때 데이터를 꺼내오는 경우이다. 앞서 살펴본 바와 같이 큐에 데이터가 딱 1개만 존재하는 경우는 front와 rear의 값이 동일한 경우이다.

따라서 두 포인터의 값이 동일한 경우, 이를 다시 초기화시켜 두 포인터의 값을 0으로 유지시켜주어야 한다.
이 과정을 통해 데이터를 삽입하는 과정에서, 큐에 데이터가 아무 것도 없을 경우 무조건 0번 위치부터 데이터 삽입을 할 수 있도록 분기점을 통일시켜줄 수 있다.

class Queue {
					...
	deQueue() {
    	let temp;
     	if (this.front === this.rear) {
        	temp = this.storage[this.front];
          	delete this.storage[this.front];
          	this.front = 0;
          	this.reear = 0;
        } else {
        	temp = this.storage[this.front];
          	delete this.storage[this.front];
          	this.front += 1;
        }
      	return temp;
    }
}