C++ STL(표준 템플릿 라이브러리)은 다양한 컨테이너 어댑터(container adapter)를 제공하는데, 그중 priority_queue(우선순위 큐)는 항상 큐의 첫 번째 원소가 전체 원소 중 가장 큰 값을 갖도록 관리하는 자료구조입니다. 우선순위가 높은 원소가 낮은 원소보다 먼저 처리되며, 내부적으로는 힙(heap) 알고리즘을 통해 정렬 상태가 유지됩니다.
주요 멤버 함수
이번 예제에서 사용하는 priority_queue의 대표 함수는 다음과 같습니다.
- pq.size() : 큐에 저장된 원소의 개수를 반환합니다.
- pq.push(value) : 큐에 새 원소를 삽입하고, 힙 구조가 유지되도록 재배치합니다.
- pq.pop() : 최상단(우선순위가 가장 높은) 원소를 제거합니다.
- pq.top() : 최상단 원소에 대한 참조를 반환합니다.
- pq.empty() : 큐가 비어 있으면 true, 그렇지 않으면 false를 반환합니다.
전체 예제 코드
아래 프로그램은 사용자에게 메뉴를 출력하고, 선택에 따라 원소 삽입, 삭제, 최상단 원소 확인, 크기 확인 기능을 반복 수행합니다.
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
int main() {
priority_queue<int> pq;
int c, i;
while (1) {
cout<<"1.Size of the Priority Queue"<<endl;
cout<<"2.Insert Element into the Priority Queue"<<endl;
cout<<"3.Delete Element from the Priority Queue"<<endl;
cout<<"4.Top Element of the Priority Queue"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>c;
switch (c) {
case 1:
cout<<"Size of the Queue: "<<pq.size()<<endl;
break;
case 2:
cout<<"Enter value to be inserted: ";
cin>>i;
pq.push(i);
break;
case 3:
if (!pq.empty()) {
i = pq.top();
pq.pop();
cout<<i<<" Deleted"<<endl;
} else {
cout<<"Priority Queue is Empty"<<endl;
}
break;
case 4:
if (!pq.empty()) {
cout<<"Top Element of the Queue: "<<pq.top()<<endl;
} else {
cout<<"Priority Queue is Empty"<<endl;
}
break;
case 5:
exit(0);
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
코드 설명
- 무한 루프 안에서 메뉴를 출력하고 사용자 입력을 받아 switch문으로 분기합니다.
- 메뉴 1은
size()로 현재 큐에 들어 있는 원소 개수를 출력합니다. - 메뉴 2는 값을 입력받아
push()로 큐에 삽입합니다. - 메뉴 3은 큐가 비어 있는지 먼저 확인한 뒤, 비어 있지 않으면
top()으로 값을 읽어 출력하고pop()으로 삭제합니다. - 메뉴 4는
top()으로 현재 최댓값을 확인합니다. - 메뉴 5는 프로그램을 종료합니다.
팁: 빈 큐에서 top()이나 pop()을 호출하는 것은 정의되지 않은 동작(undefined behavior)이므로, 위 코드처럼 반드시 empty() 검사를 먼저 수행하는 것이 좋습니다. 또한 각 case 끝에는 break;를 빠뜨리지 않아야 의도하지 않은 흐름(fall-through)을 방지할 수 있습니다.
실행 결과 예시
1.Size of the Priority Queue 2.Insert Element into the Priority Queue 3.Delete Element from the Priority Queue 4.Top Element of the Priority Queue 5.Exit Enter your Choice: 2 Enter value to be inserted: 1 Enter your Choice: 2 Enter value to be inserted: 7 Enter your Choice: 2 Enter value to be inserted: 6 Enter your Choice: 4 Top Element of the Queue: 7 Enter your Choice: 3 7 Deleted Enter your Choice: 4 Top Element of the Queue: 6 Enter your Choice: 1 Size of the Queue: 2 Enter your Choice: 5
삽입 순서와 무관하게 항상 가장 큰 값(7 → 6)이 먼저 처리되는 것을 확인할 수 있습니다.
마무리 및 참고 사항
priority_queue 주요 연산의 시간 복잡도는 다음과 같습니다.
- 삽입(push) : O(log N)
- 삭제(pop) : O(log N)
- 최상단 조회(top) : O(1)
기본 priority_queue는 최대 힙(max-heap)으로 동작하지만, 아래처럼 선언하면 최솟값이 먼저 나오는 최소 힙(min-heap)으로 바꿀 수 있습니다. 이 경우 <vector>와 <functional> 헤더가 필요합니다.
priority_queue<int, vector<int>, greater<int>> min_pq;
이처럼 STL의 priority_queue를 활용하면 힙을 직접 구현하지 않고도 우선순위 기반 작업 스케줄링, 다익스트라(Dijkstra) 최단 경로 탐색 등 다양한 알고리즘 문제를 손쉽게 해결할 수 있습니다.