1. 컨테이너 어댑터(Container Adapter)의 개념

C++ STL에서 스택(Stack), 큐(Queue), 우선순위 큐(Priority Queue)는 독립적인 자료구조라기보다 기존 컨테이너의 인터페이스를 제한하거나 변형하여 특정 목적에 맞게 재설계한 컨테이너 어댑터로 분류됩니다. 이들은 내부적으로 데이터를 저장하기 위해 vector, list, deque와 같은 표준 시퀀스 컨테이너를 사용합니다.

2. Stack(스택)

스택은 후입선출(LIFO, Last-In-First-Out) 원칙을 따르는 자료구조입니다. 한쪽 끝(Top)에서만 데이터의 삽입과 삭제가 이루어지며, 중간 요소에 직접 접근하거나 순회하는 것이 제한됩니다.

주요 인터페이스

• push(): 데이터 삽입
• pop(): 데이터 삭제 (가장 최근 데이터)
• top(): 가장 위쪽 데이터 참조
• empty(): 비어있는지 확인

#include <iostream>
#include <stack>
#include <vector>

void demo_stack() {
    // 기본적으로 deque를 사용하지만 vector를 기반으로 생성 가능
    std::stack<int, std::vector<int>> s;

    for (int i = 10; i <= 50; i += 10) {
        s.push(i);
    }

    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
}

3. Queue(큐)

큐는 선입선출(FIFO, First-In-First-Out) 구조입니다. 데이터는 뒤(Back)로 들어가서 앞(Front)으로 나옵니다. 스택과 마찬가지로 중간 요소에 접근할 수 없습니다.

주요 인터페이스

• push(): 뒤쪽에 데이터 추가
• pop(): 앞쪽 데이터 삭제
• front()/back(): 앞/뒤 요소 참조

#include <iostream>
#include <queue>
#include <list>

void demo_queue() {
    // list를 기반 컨테이너로 사용하는 큐
    std::queue<int, std::list<int>> q;

    q.push(100);
    q.push(200);
    q.push(300);

    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
}

4. Deque(데크): 어댑터의 기본 엔진

stack과 queue의 기본 기반 컨테이너인 deque(Double-Ended Queue)는 양방향에서 삽입과 삭제가 O(1)에 가능한 연속 메모리 지향 구조입니다. vector에 비해 앞부분 삽입/삭제 성능이 뛰어나며, 메모리 확장이 조각 단위로 이루어져 재할당 비용이 분산되는 장점이 있습니다. 다만, 메모리 연속성이 완전하지 않아 임의 접근(Indexing) 성능은 vector보다 미세하게 느립니다.

5. Priority Queue(우선순위 큐)

우선순위 큐는 일반적인 큐와 달리 데이터의 우선순위에 따라 출력이 결정됩니다. 내부적으로 힙(Heap) 구조를 사용하여 가장 큰(또는 작은) 요소를 Top에 유지합니다.

우선순위 큐의 동작 방식

내부적으로 push 호출 시 push_heap 알고리즘을, pop 호출 시 pop_heap 알고리즘을 사용하여 힙 성질을 유지합니다.

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

void demo_priority_queue() {
    // 최소 힙(Min-heap) 구성
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(20);

    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " "; // 10 20 30 출력
        min_heap.pop();
    }
}

6. 우선순위 큐의 직접 구현 및 펑터(Functor)

우선순위 큐를 직접 구현할 때는 비교 로직을 유연하게 처리하기 위해 펑터(함수 객체)를 활용합니다.

#include <vector>
#include <algorithm>

namespace custom {
    template<typename T>
    struct Less {
        bool operator()(const T& a, const T& b) const { return a < b; }
    };

    template<typename T, typename Container = std::vector<T>, typename Compare = Less<T>>
    class PriorityQueue {
    public:
        void push(const T& val) {
            storage_.push_back(val);
            sift_up(storage_.size() - 1);
        }

        void pop() {
            if (storage_.empty()) return;
            std::swap(storage_[0], storage_.back());
            storage_.pop_back();
            sift_down(0);
        }

        const T& top() const { return storage_[0]; }
        bool empty() const { return storage_.empty(); }

    private:
        Container storage_;
        Compare comp_;

        void sift_up(size_t idx) {
            while (idx > 0) {
                size_t parent = (idx - 1) / 2;
                if (comp_(storage_[parent], storage_[idx])) {
                    std::swap(storage_[parent], storage_[idx]);
                    idx = parent;
                } else break;
            }
        }

        void sift_down(size_t idx) {
            size_t child = idx * 2 + 1;
            while (child < storage_.size()) {
                if (child + 1 < storage_.size() && comp_(storage_[child], storage_[child + 1])) {
                    child++;
                }
                if (comp_(storage_[idx], storage_[child])) {
                    std::swap(storage_[idx], storage_[child]);
                    idx = child;
                    child = idx * 2 + 1;
                } else break;
            }
        }
    };
}

7. 실전 응용: K번째로 큰 요소 찾기

우선순위 큐는 대량의 데이터에서 상위 K개의 데이터를 추출할 때 효율적입니다. 정렬(O(N log N))보다 메모리와 시간 효율이 좋은 O(N log K) 방식으로 해결할 수 있습니다.

#include <vector>
#include <queue>

int get_kth_largest(std::vector<int>& nums, int k) {
    // 최소 힙을 유지하여 상위 k개만 남김
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int n : nums) {
        pq.push(n);
        if (pq.size() > k) {
            pq.pop();
        }
    }
    return pq.top();
}