🚦 Priority Queue
우선순위를 가진 항목들을 저장하는 큐
- FIFO가 아니라 우선 순위가 높은 데이터가 먼저 나간다.
Priority Queue의 연산
- insert
우선순위 큐에 요소를 추가한다.
- delete
우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
- find
우선순위가 가장 높은 요소를 반환한다.
- isEmpty
우선순위 큐가 비어있는지 확인한다.
Priority Queue의 구분
Priority Queue의 응용 분야
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링
Priority Queue의 구현 방법
- 배열(array)
- 연결리스트(linked list)
- 힙(heap)
구현 방법 | 삽입 | 삭제 |
---|
순서 없는 배열 | O(1) | O(n) |
순서 없는 연결리스트 | O(1) | O(n) |
정렬된 배열 | O(n) | O(1) |
정렬된 연결리스트 | O(n) | O(1) |
힙 | O(log n) | O(log n) |