[JS] 자바스크립트로 우선순위 큐(Priority Queue) 구현하기

우선순위 큐(Priority Queue)란?

우선순위를 고려해 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료구조이다.

정렬 방식으로 배열 기반, 연결리스트 기반, 힙(Heap) 기반 등이 존재한다.

---

구현할 메서드(method)

데이터 전체 반환

PriorityQueue.getBuffer()

비어 있는지 확인

PriorityQueue.isEmpty()

데이터 추가 / 데이터 삭제

PriorityQueue.enqueue() / PriorityQueue.dequeue()

첫 번째 데이터 조회

PriorityQueue.front()

데이터 개수 확인

PriorityQueue.size()

데이터 전체 삭제

PriorityQueue.clear()

---

우선순위 큐 구현 - getBuffer(), isEmpty()

// 데이터와 우선순위를 저장하기 위한 생성자 함수
function Element(data, priority) {
  this.data = data;
  this.priority = priority;
}

// Element 관리를 위한 생성자 함수
function PriorityQueue() {
  this.array = [];
}

// 객체 내 데이터 셋 반환
PriorityQueue.prototype.getBuffer = function () {
  return this.array.map((element) => element.data);
};

// 객체 내 데이터 존재 여부 확인
PriorityQueue.prototype.isEmpty = function () {
  return this.array.length === 0;
};

console.log(Object.getOwnPropertyDescriptors(Element.prototype));
// {
//     constructor: {
//       value: [Function: Element],
//       writable: true,
//       enumerable: false,
//       configurable: true
//     }
//   }
console.log(Object.getOwnPropertyDescriptors(PriorityQueue.prototype));
// {
//     constructor: {
//       value: [Function: PriorityQueue],
//       writable: true,
//       enumerable: false,
//       configurable: true
//     },
//     getBuffer: {
//       value: [Function (anonymous)],
//       writable: true,
//       enumerable: true,
//       configurable: true
//     },
//     isEmpty: {
//       value: [Function (anonymous)],
//       writable: true,
//       enumerable: true,
//       configurable: true
//     }
//   }

우선순위 큐 구현 - enqueue(), dequeue()

// 데이터 추가
PriorityQueue.prototype.enqueue = function (data, priority) {
  let element = new Element(data, priority);
  let added = false;

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

  if (!added) {
    this.array.push(element);
  }

  return this.array.length;
};

// 데이터 삭제
PriorityQueue.prototype.dequeue = function () {
  return this.array.shift();
};

let pq = new PriorityQueue();

pq.enqueue("kh", 1);
pq.enqueue("ys", 2);
console.log(pq);
// PriorityQueue {
//   array: [
//     Element { data: 'kh', priority: 1 },
//     Element { data: 'ys', priority: 2 }
//   ]
// }
pq.enqueue("alice", 1);
pq.enqueue("bob", 3);
console.log(pq);
// PriorityQueue {
//   array: [
//     Element { data: 'kh', priority: 1 },
//     Element { data: 'alice', priority: 1 },
//     Element { data: 'ys', priority: 2 },
//     Element { data: 'bob', priority: 3 }
//   ]
// }
pq.dequeue();
console.log(pq);
// PriorityQueue {
//   array: [
//     Element { data: 'alice', priority: 1 },
//     Element { data: 'ys', priority: 2 },
//     Element { data: 'bob', priority: 3 }
//   ]
// }

우선순위 큐 구현 - front(), size(), clear()

// 첫 데이터 반환
PriorityQueue.prototype.front = function () {
  return this.array.length === 0 ? undefined : this.array[0].data;
};

// 데이터 사이즈 반환
PriorityQueue.prototype.size = function () {
  return this.array.length;
};

// 데이터 초기화
PriorityQueue.prototype.clear = function () {
  this.array = [];
};

let pq = new PriorityQueue();

pq.enqueue("kh", 1);
pq.enqueue("ys", 2);
pq.enqueue("alice", 1);
pq.enqueue("bob", 3);

console.log(pq.getBuffer()); // [ 'kh', 'alice', 'ys', 'bob' ]
console.log(pq.front()); // kh
console.log(pq.size()); // 4