우선순위 큐(Priority Queue)는 일반적인 큐와 달리 각 요소가 우선순위(priority)를 가지며, 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다. 이번 글에서는 자바스크립트의 클래스와 배열을 활용해 우선순위 큐를 직접 구현하는 방법을 단계별로 살펴보겠습니다.
우선순위 큐 클래스의 주요 메서드
이번에 만들 PriorityQueue 클래스는 다음과 같은 기능들을 포함합니다.
- enqueue(element): 큐에 새로운 요소를 추가합니다.
- dequeue(): 큐에서 요소를 제거하고 반환합니다.
- peek(): 큐의 맨 앞에 있는 요소를 확인합니다.
- isFull(): 큐가 설정된 최대 용량에 도달했는지 검사합니다.
- isEmpty(): 큐가 비어 있는지 검사합니다.
- clear(): 큐의 모든 요소를 삭제합니다.
- display(): 배열에 담긴 모든 내용을 출력합니다.
클래스 기본 구조 설계
먼저, 큐의 최대 크기(maxSize)를 인자로 받는 생성자를 가진 간단한 클래스를 정의하는 것부터 시작하겠습니다. 이후 다른 메서드들을 구현할 때 유용하게 사용할 헬퍼 함수도 함께 만들어 둡니다.
또한 스택(Stack)을 구현할 때와 마찬가지로, 우선순위 큐 역시 배열(Array)을 기반으로 구현합니다. 각 노드의 데이터(data)와 우선순위(priority)를 저장하기 위해 PriorityQueue 클래스의 프로토타입에 별도의 내부 구조체(Element 클래스)도 정의해야 합니다.
예제 코드
class PriorityQueue {
constructor(maxSize) {
// maxSize가 전달되지 않으면 기본값 10으로 설정
if (isNaN(maxSize)) {
maxSize = 10;
}
this.maxSize = maxSize;
// 큐의 값을 담을 배열 초기화
this.container = [];
}
// 개발 중 값을 확인하기 위한 헬퍼 함수
display() {
console.log(this.container);
}
// 큐가 비어 있는지 확인
isEmpty() {
return this.container.length === 0;
}
// 큐가 가득 찼는지 확인
isFull() {
return this.container.length >= this.maxSize;
}
}
// 큐에 새 노드를 생성할 때 사용할 내부 클래스
// 각 요소는 데이터와 우선순위를 가짐
PriorityQueue.prototype.Element = class {
constructor (data, priority) {
this.data = data; this.priority = priority;
}
}isFull과 isEmpty 메서드 살펴보기
위 코드에는 큐의 상태를 확인하는 두 가지 메서드인 isFull과 isEmpty가 추가로 정의되어 있습니다.
isFull 함수는 컨테이너 배열의 길이가 maxSize보다 크거나 같은지 단순히 비교한 후, 그 결과를 불리언 값으로 반환합니다. 즉, 큐가 용량을 초과했는지 여부를 판단하는 역할을 합니다.
isEmpty 함수는 컨테이너의 크기가 0인지 확인하여, 큐에 요소가 하나도 없는 상태인지를 알려줍니다.
이 두 메서드는 이후 enqueue나 dequeue 같은 핵심 연산을 구현할 때 매우 유용하게 활용됩니다. 예를 들어, 큐가 가득 찼는데 요소를 추가하려 하거나, 빈 큐에서 요소를 꺼내려 할 때 오류를 방지하는 가드(guard) 역할을 수행합니다. 앞으로 정의할 나머지 메서드들도 모두 PriorityQueue 클래스 내부에 추가될 예정입니다.