[자료구조] 우선순위 큐(Priority Queue) 메서드 구현하기

🫠 큐에 우선순위를 두면 어떻게 될까? 큐의 대표적인 특징인 FIFO에서 데이터에 우선순위를 넣어, 우선순위를 고려한 데이터가 먼저 나오는 FIFO 기반의 선형 자료 구조를 만들어보자!

 

 

 

🫠 우선순위가 포함된 큐 생성자 함수를 만들어보자

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


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


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

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

✅ Element 생성자 함수는 element에 data와 priority 즉, 우선순위만 저장해 주는 역할을 한다.
✅ 실제 Element를 관리해주는 함수는 PriorityQueue()가 해당
✅ getBuffer() 메서드에서 slice()를 사용하지 않고, map()을 통해 배열 내에 요소를 순차적으로 하나씩 돌아 data를 복사한다.
✅ isEmpty()는 변경된 코드 없이 똑같이 사용할 수 있다.

 

 

 

❗️ Element 생성자 함수와 PriorityQueue 생성자 함수의 메서드를 출력해 보자

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

✅ Element 생성자 함수 data와 priority만 저장하기 때문에 다른 메서드는 없는 것을 확인할 수 있다.
✅ PriorityQueue 생성자 함수에는 getBuffer()와 isEmpty() 메서드가 있는 것을 확인할 수 있다. 

 

 

 

---

🫠 우선순위 큐 enqueue() & dequeue() 메서드 구현하기

// enqueue() : 데이터 추가
PriorityQueue.prototype.enqueue = function(data, priority){
  let element = new Element(data, priority)
  let added = false // 아직 받은 element가 없으므로

  for(let i = 0; i < this.array.length; i++){
    if(element.priority < this.array[i].priority) {// 새로 들어온 element의 숫자(우선순위)가 현재 배열에 있는 priority보다 작으면(우선순위가 높으면)
      this.array.splice(i, 0, element) // splice -> i번째에 있는 데이터를, 0개만큼 지워라, 그리고 element를 추가해라
      added = true // element를 배열에 추가했다면 true
      break // for문을 빠져나와라
    }
  }

  if(!added){ // 만약 element가 추가되지 않았다면, 맨 마지막 순위이므로 뒤에 push
    this.array.push(element)
  }

  return this.array.length
}


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

✅ 주석 처리 설명 확인
✅ splice()는 해당 위치에서부터 데이터를 지정한 개수만큼 삭제하는 것이 특징이지만, splice(i, 0, element)처럼 삭제할 데이터를 0개로 지정한 경우, 삭제되는 데이터는 없으며 element만 해당 위치에 추가된다.
✅ dequeue()는 변경된 코드 없이, 이전 시간에 작성한 코드와 같다.

 

 

 

❗️ 해당 메서드 실행해서 결과 확인해 보자

// user 객체 생성(우선순위 확인)
let user = new PriorityQueue()

user.enqueue('YJ', 1)
user.enqueue('SH', 2)
console.log(user)
/*
PriorityQueue {
  array: [
    Element { data: 'YJ', Priority: 1 },
    Element { data: 'SH', Priority: 2 }
  ]
}
*/


// user 객체에 우선순위 1과 3 추가
user.enqueue('JH', 1)
user.enqueue('HY', 3)
console.log(user)
/*
PriorityQueue {
  array: [
    Element { data: 'YJ', priority: 1 },
    Element { data: 'JH', priority: 1 },
    Element { data: 'SH', priority: 2 },
    Element { data: 'HY', priority: 3 }
  ]
}
*/


// dequeue() 실행 확인
console.log(user.dequeue()) // Element { data: 'YJ', priority: 1 }
console.log(user)
/*
PriorityQueue {
  array: [
    Element { data: 'JH', priority: 1 },
    Element { data: 'SH', priority: 2 },
    Element { data: 'HY', priority: 3 }
  ]
}
*/

✅ 두 번째 문단 enqueue() 실행 결과를 보면 처음에 추가했던 'YJ', 'SH' 사이에 'JH'가 우선순위 '1'로 인해 들어온 것을 확인할 수 있다. 'HY'는 우선순위가 가장 낮으므로 맨 끝에 추가.
✅ 세 번째 문단 dequeue()를 실행한 경우, 가장 앞 데이터인 'YJ'의 데이터가 삭제된 것을 확인할 수 있다.

 

 

 

---

❗️ 우선순위 큐의 또 다른 메서드 

// 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 = []
}


// 실행
console.log(user)
/*
PriorityQueue {
  array: [
    Element { data: 'JH', priority: 1 },
    Element { data: 'SH', priority: 2 },
    Element { data: 'HY', priority: 3 }
  ]
}
*/
console.log(user.front()) // JH
console.log(user.size()) // 3

✅ front(), size(), clear() 메서드는 기존과 같기 때문에 따로 설명은 하지 X
✅ 메서드 실행 주석 처리 확인하자