우선순위 큐(Priority Queue)

언지·2025년 4월 21일

우선순위 큐(Priority Queue)

우선순위를 고려하여 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료 구조
우선순위 정렬 방식 : 배열 기반, 연결리스트 기반, 힙(Heap) 기반 등의 정렬 방식 존재

구현 메서드 (method)

데이터 전체 획득 : PriotiyQueue.getBuffer()

데이터 비어있는지 확인 : PriotiyQueue.isEmpty()

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

// priorityQueue() : Element 관리를 위한 생성자 함수
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;
};

console.log(Object.getOwnPropertyDescriptors(Element.prototype));
console.log(Object.getOwnPropertyDescriptors(PriorityQueue.prototype));

------------------------------------------------------------------------
OUTPUT
{
  constructor: {
    value: [Function: Element],
    writable: true,
    enumerable: false,
    configurable: true
  }
}
{
  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
  }
}

데이터 추가 : PriotiyQueue.enqueue()

데이터 삭제 : PriotiyQueue.dequeue()

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

// priorityQueue() : Element 관리를 위한 생성자 함수
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;
};

// 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); // (i번째에, 삭제없이, element 추가)
      added = true;
      break;
    }
  }

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

  return this.array.length;
};

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

let pq = new PriorityQueue();
pq.enqueue("Alice", 1);
pq.enqueue("bob", 2);

console.log(pq);

pq.enqueue("Tom", 1);
pq.enqueue("John", 3);

console.log(pq);

console.log("dequeue : ", pq.dequeue());
console.log("dequeue : ", pq.dequeue());

console.log(pq);

------------------------------------------------------------------------
OUTPUT
PriorityQueue {
  array: [
    Element { data: 'Alice', priority: 1 },
    Element { data: 'bob', priority: 2 }
  ]
}
PriorityQueue {
  array: [
    Element { data: 'Alice', priority: 1 },
    Element { data: 'Tom', priority: 1 },
    Element { data: 'bob', priority: 2 },
    Element { data: 'John', priority: 3 }
  ]
}
dequeue : Element { data: 'Alice', priority: 1 }
dequeue : Element { data: 'Tom', priority: 1 }
PriorityQueue {
  array: [
    Element { data: 'bob', priority: 2 },
    Element { data: 'John', priority: 3 }
  ]
}

첫번째 데이터 : PriotiyQueue.front()
데이터 사이즈 : PriotiyQueue.size()

전체 삭제 : PriotiyQueue.clear()

// front() : 가장 첫 데이터 반환
PriorityQueue.prototype.front = function () {
  return this.array.length === 0 ? undefined : this.array[0];
};
// size() : 큐 내 데이터 개수 확인
PriorityQueue.prototype.size = function () {
  return this.array.length;
};
// clear() : 큐 초기화
PriorityQueue.prototype.clear = function () {
  return (this.array = []);
};

언지

이전 포스트

스택+큐

다음 포스트

우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

스택+큐

해시테이블

0개의 댓글