우선순위 큐(Priority Queue) 구현해보기

우선순위 큐란?

우선순위를 고려하여 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료 구조

우선순위 정렬 방식

배열 기반, 연결리스트 기반, 힙 기반 등의 정렬 방식 존재

구현 메서드

• 데이터 전체 획득 / 비어 있는지 확인: PriorityQueue.getBuffer(), PriorityQueue.isEmpty()
• 데이터 추가 / 삭제: PriorityQueue.enqueue(), PriorityQueue.dequeue()
• 첫번째 데이터 / 사이즈 / 전체 삭제: PriorityQueue.front(), PriorityQueue.size(), PriorityQueue.clear()

우선순위 큐의 사용 예시

비행기 탑승, 병원 응급실처럼 우선순위가 높은 쪽이 더 빠르게 진입하는 곳

1. 데이터와 우선 순위를 저장하기 위한 생성자 함수 (Element)

function Element(data, priority) {
    this.data = data;
    this.priority = priority;
}

2. PriorityQueue 생성

function PriorityQueue() {
    this.array = [];
}

3. 객체 내 데이터 반환 (PriorityQueue.getBuffer())

array 내부에 data와 priority를 저장한 객체가 담겨 있기 때문에 데이터만 반환하기 위해서는 map을 사용해서 element의 data를 저장해준다.

PriorityQueue.prototype.getBuffer = function() {
	return this.array.map(element => element.data);
}

4. 객체가 비었는지 확인 (PriorityQueue.isEmpty())

PriorityQueue.prototype.isEmpty = function() {
    return this.array.length == 0;
}

5. 데이터를 추가 (PriorityQueue.enqueue(element, priority))

1. element와 priority로 새로운 Element 객체를 만든다.
2. added 변수는 priority가 중간에 삽입됐는지를 확인하는 용도이다.
3. 추가 되는 element는 전체 배열을 순회하다가 array[i]priority보다 적을 경우에 해당 위치에 데이터를 삭제하기 않고 추가한다.
4. 만약 added가 false일 경우에는 array에 element를 추가한다.

PriorityQueue.prototype.enqueue = function(element, priority) {
	let element = new Element(element, priority);
	let added = false;

	for (let i = 0; i < this.length; ++i) {
		if (element.priority < this.array[i].priority) {
			this.array.splice(i, 0, element);
			added = true;
			break;
		}
	}
	if (!added) return this.array.push(element);
}

6. 데이터를 삭제 (PriorityQueue.dequeue())

PriorityQueue.prototype.dequeue = function() {
    return this.array.shift();
}

아래 3개의 메서드는 일반 queue와 동일

7. 가장 첫 데이터를 반환 (PriorityQueue.front())

PriorityQueue.prototype.front = function() {
    return this.array.length === 0 ? undefined : this.array[0].data;
}

8. 큐 내 데이터의 개수를 확인 (PriorityQueue.size())

PriorityQueue.prototype.size = function() {
    return this.array.length;
}

9. 큐 초기화

PriorityQueue.prototype.clear = function() {
    return this.array = [];
}

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_PriorityQueue