큐 - 우선순위 큐(Priority Queue)

우선순위 큐 (Priority Queue)

• 우선순위 큐의 특성
  • 우선순위를 가진 항목들을 저장하는 큐
  • FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됩니다.
• 우선순위 큐의 적용 분야
  • 시뮬레이션 시스템
  • 네트워크 트랙픽 제어
  • 운영체제의 테스크 스케줄링
• 우선순위 큐의 구현
  • 배열을 이용한 우선순위 큐
  • 리스트를 이용한 우선순위 큐

---

우선순위 큐의 기본 연산

---

• 배열을 이용하여 우선순위 큐 구현
  • 배열을 이용하여 자료 저장
  • 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조
  • 가장 앞에 최고 우선순위의 원소가 위치하게 됩니다.
• 문제점
  • 배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생합니다.
  • 이에 소요되는 시간이나 메모리 낭비가 큽니다.