자바스크립트 PriorityQueue 클래스 구현하기

우선순위 큐(Priority Queue)란?

우선순위 큐는 일반적인 큐(FIFO, 선입선출)와 달리 각 요소가 우선순위(priority)를 가지며, 우선순위에 따라 처리 순서가 결정되는 자료구조입니다. 운영체제의 작업 스케줄링, 다익스트라 최단 경로 알고리즘 등 다양한 분야에서 활용됩니다.

자바스크립트는 우선순위 큐를 기본으로 제공하지 않기 때문에 필요하다면 직접 구현해야 합니다. 아래는 ES6 클래스 문법으로 작성한 PriorityQueue 클래스의 전체 구현 예제입니다.

PriorityQueue 클래스 전체 코드

class PriorityQueue {
  constructor(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;
  }

  // 데이터와 우선순위를 받아 큐에 삽입
  enqueue(data, priority) {
    if (this.isFull()) {
      console.log('Queue Overflow!');
      return;
    }
    const currElem = new this.Element(data, priority);
    let addedFlag = false;

    // 우선순위에 따라 알맞은 위치에 삽입
    for (let i = 0; i < this.container.length; i++) {
      if (currElem.priority < this.container[i].priority) {
        this.container.splice(i, 0, currElem);
        addedFlag = true;
        break;
      }
    }
    if (!addedFlag) {
      this.container.push(currElem);
    }
  }

  // 큐에서 요소를 제거하고 반환
  dequeue() {
    if (this.isEmpty()) {
      console.log('Queue Underflow!');
      return;
    }
    return this.container.pop();
  }

  // 요소를 제거하지 않고 맨 뒤 요소만 확인
  peek() {
    if (this.isEmpty()) {
      console.log('Queue Underflow!');
      return;
    }
    return this.container[this.container.length - 1];
  }

  // 큐 전체 비우기
  clear() {
    this.container = [];
  }
}

// 큐에 새 노드를 만들 때 사용하는 내부 클래스
// 각 요소는 데이터(data)와 우선순위(priority)를 가진다
PriorityQueue.prototype.Element = class {
  constructor(data, priority) {
    this.data = data;
    this.priority = priority;
  }
};

주요 메서드 살펴보기

constructor(maxSize)

큐의 최대 크기를 설정합니다. 인자가 전달되지 않거나 숫자가 아니면 기본값인 10으로 초기화되며, 실제 데이터는 내부 배열 container에 저장됩니다.

isEmpty() / isFull()

isEmpty()는 큐가 비어 있는지, isFull()은 큐가 가득 찼는지 여부를 불리언 값으로 반환합니다. 삽입·삭제 연산 전에 큐의 상태를 검사하는 용도로 사용됩니다.

enqueue(data, priority)

데이터와 우선순위를 받아 새 요소(Element)를 생성한 뒤 큐에 삽입합니다. 이미 저장된 요소들의 우선순위와 비교하여 자신보다 우선순위 값이 큰 요소 앞에 splice()로 삽입되므로, 큐는 항상 우선순위 순으로 정렬된 상태를 유지합니다. 큐가 가득 찬 경우에는 'Queue Overflow!' 메시지를 출력하고 삽입을 중단합니다.

dequeue()

배열의 맨 뒤에서 요소를 제거하고 반환합니다(pop()). 큐가 비어 있으면 'Queue Underflow!' 메시지를 출력합니다.

peek()

요소를 제거하지 않고 맨 뒤(다음으로 처리될) 요소만 확인합니다.

clear()

내부 배열을 비워 큐를 초기화합니다.

사용 예제

const pq = new PriorityQueue();

// 우선순위 값이 클수록 먼저 처리됩니다
pq.enqueue('여유로운 작업', 1);
pq.enqueue('보통 작업', 5);
pq.enqueue('긴급 작업', 10);

pq.display();
// [{data: '여유로운 작업', priority: 1}, {data: '보통 작업', priority: 5}, {data: '긴급 작업', priority: 10}]

console.log(pq.dequeue().data); // '긴급 작업'
console.log(pq.peek().data);    // '보통 작업'

이처럼 PriorityQueue 클래스를 활용하면 우선순위 기반 작업 처리 로직을 손쉽게 구현할 수 있습니다. 다만 위 구현은 삽입 시 선형 탐색을 사용하므로 O(n)의 시간 복잡도를 가지며, 대용량 데이터를 다루는 성능이 중요한 환경에서는 이진 힙(binary heap) 기반 구현을 고려하는 것이 좋습니다.

자바스크립트 PriorityQueue 클래스 구현하기 – 우선순위 큐 완벽 가이드