C++ 덱(Deque)과 우선순위 큐(Priority Queue) 완벽 정리

큐(Queue) 자료구조는 선입선출(FIFO, First In First Out) 방식으로 동작하는 것으로 잘 알려져 있습니다. 하지만 큐에는 몇 가지 변형된 형태가 존재하는데, 대표적인 것이 바로 덱(Deque)과 우선순위 큐(Priority Queue)입니다.

덱(Deque)이란?

덱은 'Double Ended Queue'의 줄임말로, 양방향 큐를 의미합니다. 일반적인 큐와 달리 앞(front)과 뒤(back) 양쪽 끝에서 모두 삽입과 삭제가 가능한 구조입니다. 즉, 한 쌍의 포인터는 왼쪽 방향의 데이터를 관리하고, 다른 한 쌍은 오른쪽 방향의 데이터를 관리하게 됩니다.

C++ STL에서는 <deque> 헤더를 통해 덱 기능을 손쉽게 사용할 수 있습니다. 아래 예제 코드를 통해 덱의 주요 동작을 살펴보겠습니다.

예제 코드 (Deque)

#include <iostream>
#include <deque>
using namespace std;

void printDeque(deque<int> que) {
    deque<int>::iterator it;
    for (it = que.begin(); it != que.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

int main() {
    deque<int> que;
    que.push_back(10);   // 뒤쪽에 삽입
    que.push_front(20);  // 앞쪽에 삽입
    que.push_back(30);
    que.push_front(15);

    cout << "현재 큐의 상태 : ";
    printDeque(que);

    cout << "덱의 크기 : " << que.size() << endl;
    cout << "인덱스 2 위치의 요소 : " << que.at(2) << endl;
    cout << "맨 앞 요소 : " << que.front() << endl;
    cout << "맨 뒤 요소 : " << que.back() << endl;

    cout << "앞쪽에서 삭제 : ";
    que.pop_front();
    printDeque(que);

    cout << "뒤쪽에서 삭제 : ";
    que.pop_back();
    printDeque(que);
}

실행 결과

현재 큐의 상태 : 15 20 10 30
덱의 크기 : 4
인덱스 2 위치의 요소 : 10
맨 앞 요소 : 15
맨 뒤 요소 : 30
앞쪽에서 삭제 : 20 10 30
뒤쪽에서 삭제 : 20 10

우선순위 큐(Priority Queue)란?

큐의 또 다른 변형은 우선순위 큐입니다. 이 구조에서는 큐의 각 요소가 고유한 우선순위(priority)를 가집니다. 요소를 삽입할 때 우선순위 값을 함께 지정하며, 삭제 시에는 항상 우선순위가 가장 높은 요소부터 먼저 제거됩니다. 우선순위 큐를 구현하는 가장 효율적이고 일반적인 방법 중 하나는 힙(Heap) 자료구조를 활용하는 것입니다.

C++ STL에서는 <queue> 헤더의 priority_queue를 사용할 수 있습니다. 기본 설정에서는 값이 클수록 높은 우선순위를 갖도록 동작하므로, 가장 큰 값이 항상 맨 위(top)에 위치하게 됩니다.

예제 코드 (Priority Queue)

#include <iostream>
#include <queue>
using namespace std;

void printQueue(priority_queue<int> que) {
    priority_queue<int> q = que;
    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    priority_queue<int> que;
    que.push(10);
    que.push(20);
    que.push(30);
    que.push(5);
    que.push(1);

    cout << "현재 큐의 상태 : ";
    printQueue(que);

    cout << "큐의 크기 : " << que.size() << endl;
    cout << "최상위(top) 요소 : " << que.top() << endl;

    cout << "큐에서 삭제 : ";
    que.pop();
    printQueue(que);

    cout << "큐에서 삭제 : ";
    que.pop();
    printQueue(que);
}

실행 결과

현재 큐의 상태 : 30 20 10 5 1
큐의 크기 : 5
최상위(top) 요소 : 30
큐에서 삭제 : 20 10 5 1
큐에서 삭제 : 10 5 1

정리

덱은 양방향으로 삽입·삭제가 가능한 유연한 자료구조이며, 우선순위 큐는 요소의 우선순위에 따라 처리 순서가 결정되는 자료구조입니다. 두 구조 모두 C++ STL을 통해 간편하게 활용할 수 있으므로, 상황에 맞게 적절히 선택하여 사용하면 됩니다.