이 튜토리얼에서는 C++의 set 컨테이너를 활용하여 양방향 우선순위 큐(Double-Ended Priority Queue)를 구현하는 방법을 알아보겠습니다.
양방향 우선순위 큐란?
양방향 우선순위 큐는 최솟값과 최댓값 모두 양쪽 끝에서 효율적으로 조회하고 삭제할 수 있는 자료구조입니다. C++ STL의 set은 내부적으로 균형 이진 탐색 트리를 기반으로 동작하기 때문에 요소가 항상 정렬된 상태로 유지되며, 삽입·삭제·탐색이 모두 O(log n) 시간 복잡도로 처리됩니다. 이러한 특성 덕분에 set만 있으면 양방향 우선순위 큐를 아주 간단하게 만들 수 있습니다.
구현 단계
원하는 이름으로 구조체(struct)를 생성합니다.
set을 사용해 큐 역할을 할 멤버 변수를 선언합니다.
큐의 크기를 반환하는 size 메서드를 작성합니다.
큐가 비어 있는지 여부를 확인하는 is_empty 메서드를 작성합니다.
새로운 요소를 큐에 삽입하는 insert 메서드를 작성합니다.
왼쪽 끝(최솟값)의 요소를 반환하는 get_start 메서드를 작성합니다.
오른쪽 끝(최댓값)의 요소를 반환하는 get_end 메서드를 작성합니다.
왼쪽 끝의 첫 번째 요소를 삭제하는 delete_start 메서드를 작성합니다.
오른쪽 끝의 첫 번째 요소를 삭제하는 delete_end 메서드를 작성합니다.
예제 코드
이제 전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct doubleEndedQueue {
set<int> s;
int size() {
return s.size();
}
string is_empty() {
return s.size() == 0 ? "True" : "False";
}
void insert(int x) {
s.insert(x);
}
int get_start() {
return *(s.begin());
}
int get_end() {
return *(s.rbegin());
}
void delete_start() {
if (s.size() == 0) {
return;
}
s.erase(s.begin());
}
void delete_end() {
if (s.size() == 0) {
return;
}
auto end = s.end();
end--;
s.erase(end);
}
};
int main() {
doubleEndedQueue d;
cout << "is empty: " << d.is_empty() << endl;
d.insert(1);
d.insert(2);
d.insert(3);
d.insert(4);
d.insert(5);
cout << "is empty: " << d.is_empty() << endl;
cout << "end: " << d.get_end() << endl;
d.delete_end();
cout << "end: " << d.get_end() << endl;
cout << "start: " << d.get_start() << endl;
d.delete_start();
cout << "start: " << d.get_start() << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
is empty: True is empty: False end: 5 end: 4 start: 1 start: 2
동작 원리
get_start()는 set의 가장 앞 원소, 즉 최솟값을 반환하고, get_end()는 역방향 반복자(rbegin)를 통해 최댓값을 반환합니다. 삭제 연산에서는 큐가 비어 있는 경우를 먼저 확인해 안전하게 처리한 뒤, erase 함수로 해당 위치의 원소를 제거합니다. 이렇게 하면 잘못된 반복자 접근으로 인한 런타임 오류를 예방할 수 있습니다.
마무리
이번 튜토리얼에서는 C++의 set을 활용해 양방향 우선순위 큐를 구현해 보았습니다. 한 가지 참고할 점은 set은 중복 값을 허용하지 않기 때문에, 중복 요소도 함께 저장해야 하는 상황이라면 multiset을 사용하는 것이 더 적합합니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요!