1. stack의 특징과 활용

C++ STL의 stack은 LIFO(Last-In-First-Out, 후입선출) 원칙을 따르는 컨테이너 어댑터입니다. 데이터의 삽입과 삭제가 한쪽 끝(Top)에서만 이루어지는 구조를 가집니다.

1.1 stack의 주요 인터페이스

1.2 실전 예제: 최소값을 유지하는 스택(Min Stack)

스택의 기본 기능과 더불어 현재 스택 내의 최소값을 상시 O(1)에 조회할 수 있는 구조입니다.

#include <stack>
#include <algorithm>

class CustomMinStack {
public:
    void push(int val) {
        main_stk.push(val);
        // 최소값 스택이 비었거나 새로운 값이 현재 최소값보다 작거나 같으면 기록
        if (min_stk.empty() || val <= min_stk.top()) {
            min_stk.push(val);
        }
    }

    void pop() {
        if (main_stk.top() == min_stk.top()) {
            min_stk.pop();
        }
        main_stk.pop();
    }

    int top() { return main_stk.top(); }
    int getMin() { return min_stk.top(); }

private:
    std::stack<int> main_stk;
    std::stack<int> min_stk;
};

2. queue의 특징과 활용

queue는 FIFO(First-In-First-Out, 선입선출) 구조를 가지며, 데이터는 뒤(Back)로 들어가고 앞(Front)으로 나오는 형태입니다.

2.1 queue의 주요 인터페이스

2.2 queue의 시뮬레이션 구현

큐는 앞부분의 삭제(pop_front)가 빈번하므로 std::list나 std::deque를 기반으로 구현하는 것이 효율적입니다.

#include <list>

namespace my_std {
    template<typename T, typename Container = std::list<T>>
    class queue {
    public:
        void push(const T& x) { storage.push_back(x); }
        void pop() { storage.pop_front(); }
        T& front() { return storage.front(); }
        T& back() { return storage.back(); }
        bool empty() const { return storage.empty(); }
        size_t size() const { return storage.size(); }
    private:
        Container storage;
    };
}

3. priority_queue의 이해

priority_queue는 모든 요소 중에서 우선순위가 가장 높은 요소가 항상 맨 앞에 위치하도록 설계된 컨테이너 어댑터입니다. 기본적으로 힙(Heap) 구조를 사용합니다.

3.1 사용자 정의 객체 정렬

기본적으로는 최대 힙(Max Heap)으로 동작하지만, 비교 연산자를 오버로딩하여 최소 힙(Min Heap)으로 변경할 수 있습니다.

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

struct Task {
    int id;
    int priority;

    // 우선순위가 높은(값이 큰) 것이 먼저 나오도록 설정
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

void checkPriority() {
    std::priority_queue<Task> pq;
    pq.push({1, 10});
    pq.push({2, 50});
    pq.push({3, 30});

    // priority가 50인 Task 2가 가장 먼저 출력됨
    std::cout << "Top ID: " << pq.top().id << std::endl;
}

3.2 힙 알고리즘을 이용한 직접 구현

우선순위 큐는 내부적으로 push_heap과 pop_heap 원리를 따릅니다.

#include <vector>
#include <algorithm>

template<typename T, typename Container = std::vector<T>, typename Compare = std::less<T>>
class my_priority_queue {
public:
    void push(const T& x) {
        data.push_back(x);
        shiftUp(data.size() - 1);
    }

    void pop() {
        if (data.empty()) return;
        std::swap(data[0], data[data.size() - 1]);
        data.pop_back();
        shiftDown(0);
    }

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

private:
    Container data;
    Compare comp;

    void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (comp(data[parent], data[child])) {
                std::swap(data[child], data[parent]);
                child = parent;
                parent = (child - 1) / 2;
            } else break;
        }
    }

    void shiftDown(int parent) {
        size_t child = parent * 2 + 1;
        while (child < data.size()) {
            if (child + 1 < data.size() && comp(data[child], data[child + 1])) {
                child++;
            }
            if (comp(data[parent], data[child])) {
                std::swap(data[parent], data[child]);
                parent = child;
                child = parent * 2 + 1;
            } else break;
        }
    }
};

4. 컨테이너 어댑터와 deque

STL에서 stack과 queue는 컨테이너 어댑터로 분류됩니다. 이는 독자적인 데이터 구조를 갖기보다는 기존의 vector, list, deque 등을 내부 컨테이너로 활용하여 특정 인터페이스만을 노출하기 때문입니다.

4.1 왜 deque가 기본 컨테이너인가?

std::deque(double-ended queue)는 다음과 같은 이유로 stack과 queue의 기본 기반 컨테이너로 선택됩니다.

• 효율적인 메모리 관리: vector처럼 단일 연속 메모리를 할당하지 않고, 여러 메모리 블록을 관리하므로 확장이 유연합니다.
• 양단 삽입/삭제 성능: 앞뒤 모든 방향에서 O(1) 성능을 보장하므로 queue의 pop_front 연산에 최적화되어 있습니다.
• 중간 삽입의 부재: 어차피 stack과 queue는 중간 데이터 접근을 허용하지 않으므로, deque의 단점인 복잡한 반복자 연산이 문제가 되지 않습니다.

4.2 어댑터 구조의 유연성

사용자는 다음과 같이 필요에 따라 기반 컨테이너를 변경할 수 있습니다.

#include <stack>
#include <vector>
#include <list>

// vector를 기반으로 하는 stack
std::stack<int, std::vector<int>> v_stack;

// list를 기반으로 하는 queue
std::queue<int, std::list<int>> l_queue;