자바스크립트 자료구조 우선순위 큐 메서드 정리

우선순위 큐 (Priority Queue)

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

* 일반 큐와 다른점은 무조건 적으로 먼저 넣은 데이터가 나오게 아니라 우선 순위를 정렬하여 나오게 된다.

 

- 우선 수위 정렬 방식 : 배열 기반, 연결리스트 기반, 힙(Heap)기반 등의 정렬 방식이 존재

---

구현 메서드

// Element(): 데이터와 우선순위를 저장히기 위한 생성자 함수

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

- data, priority의 필드를 설정해준다.

---

// PriorityQueue(): Element 관리를 위한 생성자 함수

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

- 핸들링 할 우선 순위 큐를 생성자함수로 만들어준다. 배열로!

---

// getBuffer(): 객체 내 데이터 셋 반환

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

- map을 통해서 객체내에 있는 요소들을 하나씩 data에 넣어준다.

---

// isEmpty(): 객체 내 데이터 존재 여부 파악

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

---

// enqueue(): 데이터 추가

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;
};

- element 에 새로운 element를 넣어준다.

- added변수는 false를 가지고 있다.

- array.length만큼 for문을 돌면서 우선순위를 비교한다.

- if element의 우선순위보다 array에 있는 우선순위가 높을때까지 순회하고 있으면 splice를 통해서 추가한다.

* splice(i, 0, element) 첫번째 요소 index, 두번째 요소 삭제할 요소, 세번째 요소 추가할 요소

- 그리고 added에 true로 할당해준다.

- for문이 끝나고 만약 added가 그대로 false라면 가장 끝에 push로 추가한다.

---

// dequeue(): 데이터 삭제

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

---

// front(): 가장 첫 데이터 반환

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

---

// size(): 큐 내 데이터 개수 반환

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

---

// clear(): 큐 초기화

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