● 우선순위 큐(priorith_queue) 컨테이너는 우선순위 queue를 구혀한 템플릿 클래스입니다. priority_queue 컨테이너에 설정된 기본 컨테이너는 vector입니다.
● priority_queue는 내부적으로 STL의 힙 알고리즘인 make_heap(), push_heap(), pop_heap()을 사용하여 구현돼 있으므로 priority_queue의 컨테이너 템플릿 인자로 받는 컨테이너는 임의 접근 반복자를 제공하는 컨테이너입니다. 또한, 이 컨테이너는 empty(), size(), push_back(), pop_back(), front() 등의 인터페이스를 제공해야 합니다. 그래서 priority_queue는 vector와 deque컨테이너는 사용할 수 있습니다
※ 다음 예제는 정수를 priority_queue 컨테이너에 저장하고 우선순위(내림차순, 오름차순 정렬)에 따라 출력하는 예제입니다
[ 우선순위 큐 예제1 ]
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pq1; //기본 정렬기준 (내림차순)
pq1.push(40);
pq1.push(20);
pq1.push(30);
pq1.push(50);
pq1.push(10);
cout << "priorith_queue[less] : " << '\n';
while(!pq1.empty())
{
cout << pq1.top() << '\n';
pq1.pop();
}
cout << "==============================" << '\n';
priority_queue<int, vector<int>, greater<int> > pq2; //오름차순 정렬
pq2.push(40);
pq2.push(20);
pq2.push(30);
pq2.push(50);
pq2.push(10);
cout << "priority_queue[greater] : " << '\n';
while(!pq2.empty())
{
cout << pq2.top() << '\n';
pq2.pop();
}
return 0;
}
※ pq1은 vector<int> 컨테이너를 사용하고 기본정렬 기준은 내림차순으로 출력하는 priority_queue 컨테이너입니다.
priority_queue<int> pq1; //기본 정렬기준 내림차순 |
※ pq2는 vector<int> 컨테이너를 사용하고 오름차순 정렬 기준을 사용한 priority_queue 입니다.
priority_queue<int, vector<int>, greater<int> > pq2; //오름차순 정렬 |
※ 인터페이스는 stack과 비슷합니다.
[ 우선순위 큐 예제2 ]
※ 우선순위 큐에 pair를 사용하여 정수2개를 저장해서 사용해보는 예제입니다
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> ci;
struct compare
{
bool operator() (ci a, ci b)
{
if(a.second > b.second) return 1;
else return 0;
}
};
int main()
{
int a, b, i;
ci t;
priority_queue<ci> pq1; //첫번째 항목으로 내림차순
pq1.push(make_pair(3,40));
pq1.push(make_pair(5,20));
pq1.push(make_pair(2,10));
pq1.push(make_pair(4,50));
pq1.push(make_pair(1,30));
while(pq1.size())
{
t = pq1.top();
cout << t.first << ' '<< t.second << '\n';
pq1.pop();
};
cout << "========================" << '\n';
priority_queue<ci, vector<ci>, greater<ci> > pq2; //첫번째 항목으로 오름차순
pq2.push(make_pair(3,40));
pq2.push(make_pair(5,20));
pq2.push(make_pair(2,10));
pq2.push(make_pair(4,50));
pq2.push(make_pair(1,30));
while(pq2.size())
{
t = pq2.top();
cout << t.first << ' '<< t.second << '\n';
pq2.pop();
};
cout << "========================" << '\n';
priority_queue<ci, vector<ci>, compare > pq3; //두번째 항목정렬
pq3.push(make_pair(3,40));
pq3.push(make_pair(5,20));
pq3.push(make_pair(2,10));
pq3.push(make_pair(4,50));
pq3.push(make_pair(1,30));
while(pq3.size())
{
t = pq3.top();
cout << t.first << ' '<< t.second << '\n';
pq3.pop();
};
return 0;
}
※ pq1은 pair를 사용해서 2개를 저장해서 첫번째 항목기준으로 내림차순으로 출력하는 priority_queue 컨테이너입니다.
priority_queue<ci> pq1; //첫번째 항목으로 내림차순 |
※ pq2은 pair를 사용해서 2개를 저장해서 첫번째 항목기준으로 오름차순으로 출력하는 priority_queue 컨테이너입니다.
priority_queue<ci, vector<ci>, greater<ci> > pq2; //첫번째 항목으로 오름차순 |
※ pq3은 pair를 사용해서 2개를 저장해서 두번째 항목기준으로 오름차순으로 출력하는 priority_queue 컨테이너입니다.
priority_queue<ci, vector<ci>, compare > pq3; //두번째 항목정렬 |
'C++ STL' 카테고리의 다른 글
21. C++ STL deque이란 (0) | 2020.06.25 |
---|---|
20. c++ STL [vector 1일차 ] vector란? (0) | 2020.06.25 |
18. c++ STL [vector 5일차] 2차원 vector (0) | 2020.04.30 |
17. c++ stl find_first_of() for_each() 알고리즘 (0) | 2020.04.16 |
16. c++ stl find(), find_if(), find_end() - 문제12 (0) | 2020.04.06 |