| 자료구조 | 처리순서 |
|---|---|
| Stack | LIFO : 나중에 들어온 데이터가 먼저 처리 |
| Queue | FIFO : 먼저 들어온 데이터가 먼저 처리 |
| Priority Queue | 우선순위가 높은 데이터가 먼저 처리 |
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저나온다.
- 시뮬레이션 시스템 (ex) 출발시간, 대기시간, 소요시간
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링
데이터를 근거로 우선순위를 판단해야하며, 목적에 맞게 우선순위를 정해야한다. 우선순위가 같은 데이터도 존재할 수 있다.
우선순위 큐에서 가장 중요한 연산은 **삽입(insert)과 삭제(delete)**이다.
| 연산 | 설명 |
|---|---|
| create() | 우선순위 큐를 생성 |
| init(q) | 우선순위 큐 q 초기화 |
| is_empty(q) | 우선순위 큐 q가 비어있는지 검사 |
| is_full(q) | 우선순위 큐 q가 가득찼는지 검사 |
| insert(q,x) | 우선순위 큐 q에 x추가 |
| delete(q) | 우선 순위큐로부터 가장 우선순위가 높은 요소 삭제, 반환 |
| find(q) | 우선순위가 가장 높은 요소 반환 |
우선순위 큐는 3가지 방법으로 구현할 수 있다.
- 배열을 기반으로 구현
- 연결리스트를 기반으로 구현
- 힙(Heap)을 이용하는 방법
배열이나 연결리스트를 이용해서 구현하면 힙보다는 간단하게 구현할 수 있으나 단점이 있다.
- 데이터 삽입 및 삭제에서 데이터를 이동하는 연산을 계속해야한다. (당기거나 밀어야하는)
- 삽입 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위를 비교해야한다.
- 삽입 위치를 찾기위해서 모든 노드에 저장된 데이터와 우선순위를 비교해야한다.
데이터가 적은 경우에는 단점이 아닐 수도 있지만 데이터가 많아지면 비교할 대상이 많아져 성능이 저하된다.
- 힙은 완전이진트리로 구현한다. 힙에 대한 자세한 설명은 힙(Heap) 게시물에서 했다.
| 표현방법 | 삽입 | 삭제 |
|---|---|---|
| 순서없는 배열 | O(1) | O(n) |
| 순서없는 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결리스트 | O(n) | O(1) |
| 힙(Heap) | O(logn) | O(logn) |
이러한 성능차이로 주로 Heap을 이용해서 우선순위큐를 구현하는 것이 일반적이다.