2026-05-20 TIL (61일차)

C++ 자료구조: Queue vs Priority Queue

오늘은 C++ 표준 템플릿 라이브러리(STL)에서 가장 자주 쓰이는 자료구조인 queue와 priority_queue의 개념과 차이, 그리고 재밌는 응용 구현까지 정리해 본다.

---

1. Queue (큐) 란?

큐는 FIFO (First-In-First-Out, 선입선출) 원칙을 따르는 자료구조다.

• 개념: 마트의 계산대 대기열이나, 롤 매칭 대기열을 생각하면 쉽다. 먼저 들어온 데이터가 먼저 나간다.
• 특징: 데이터 삽입은 항상 뒤(Back)에서 일어나고, 삭제는 항상 앞(Front)에서 일어난다.

2. Priority Queue (우선순위 큐) 란?

우선순위 큐는 들어온 순서와 상관없이 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조다.

• 개념: 응급실의 환자 대기열과 같다. 먼저 병원에 왔더라도, 위급한 환자(우선순위가 높은 데이터)가 먼저 치료(Pop)를 받는다.
• 특징: C++의 std::priority_queue는 기본적으로 내부에서 Heap(힙) 자료구조를 사용하여 구현되어 있다. 기본값은 가장 큰 값이 먼저 나오는 내림차순(Max-Heap)이다.

---

3. Queue vs Priority Queue 핵심 차이점

구분	Queue	Priority Queue
출력 순서	먼저 들어온 순서 (입력 시간 기준)	우선순위가 높은 순서 (값 기준)
내부 구현	std::deque (기본값)	std::vector를 이용한 힙(Heap) 트리
삽입 시간(Push)	O(1) (상수 시간)	O(log N) (트리 재정렬 필요)
삭제 시간(Pop)	O(1) (상수 시간)	O(log N) (트리 재정렬 필요)
최상단 확인	q.front()	pq.top()

---

4. Priority Queue 오름차순 (Min-Heap) 사용법

C++의 priority_queue는 기본적으로 가장 큰 값이 맨 위로 오는 내림차순(Max-Heap)이다. 만약 가장 작은 값이 먼저 나오게(오름차순, Min-Heap) 만들고 싶다면 선언할 때 매개변수를 추가해야 한다.

#include <queue>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    // 1. 기본 선언 (내림차순, 큰 값이 먼저 나옴)
    priority_queue<int> maxHeap; 

    // 2. 오름차순 선언 (작은 값이 먼저 나옴)
    // <자료형, 구현체(보통 vector), 비교연산자>
    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(9);

    // 출력: 1 -> 5 -> 9 순서로 나옴
    while(!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    
    return 0;
}

5. 일반 Queue 하나만 이용해서 Priority Queue 구현하기

C++ 구현 코드 (내림차순 기준)

#include <queue>
#include <iostream>

using namespace std;

// 일반 큐를 이용해 만든 커스텀 우선순위 큐 구조체
struct QueueBasedPQ {
    queue<int> q;

    // 데이터를 넣을 때 정렬을 유지하며 넣는 것이 핵심! (O(N) 시간 소요)
    void push(int val) {
        int s = q.size();
        bool inserted = false;

        // 큐의 현재 사이즈만큼 반복해서 데이터를 빼고 다시 넣는다.
        for (int i = 0; i < s; ++i) {
            // 새로 들어온 값(val)이 기존 큐의 맨 앞 값보다 크다면 (우선순위가 높다면)
            if (!inserted && val > q.front()) {
                q.push(val); // 새 값을 먼저 큐 뒤에 넣는다.
                inserted = true;
            }
            
            // 기존 값들을 빼서 다시 큐 뒤로 보낸다.
            q.push(q.front());
            q.pop();
        }

        // 만약 들어온 값이 가장 작아서 한 번도 삽입되지 않았다면 맨 뒤에 넣는다.
        if (!inserted) {
            q.push(val);
        }
    }

    void pop() {
        if (!q.empty()) q.pop();
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

int main() {
    QueueBasedPQ myPQ;
    
    myPQ.push(3);
    myPQ.push(10);
    myPQ.push(1);
    myPQ.push(7);

    // 출력: 10 -> 7 -> 3 -> 1 (우선순위 큐처럼 정확히 내림차순으로 동작!)
    while (!myPQ.empty()) {
        cout << myPQ.top() << " ";
        myPQ.pop();
    }

    return 0;
}