컨테이너 어댑터의 개념

C++ 표준 템플릿 라이브러리 (STL) 에서 스택 (stack) 과 큐 (queue) 는 독립적인 데이터 구조라기보다는 기존 컨테이너를 래핑하여 특정 접근 규칙을 강제하는 컨테이너 어댑터로 분류됩니다. 이들은 내부적으로 다른 컨테이너를 저장소로 활용하며, 사용자에게는 제한된 인터페이스만을 노출합니다.

스택 (Stack) 어댑터

동작 원리 및 정의

스택은 후입선출 (LIFO, Last In First Out) 구조를 따릅니다. 데이터의 삽입과 삭제가 항상 컨테이너의 동일한 끝단 (탑) 에서 이루어집니다. 내부 구현을 위해 다음과 같은 연산을 지원하는 시퀀스 컨테이너가 하위 저장소로 요구됩니다.

• empty: 컨테이너가 비었는지 확인
• back: 마지막 요소 참조
• push_back: 마지막 위치에 요소 삽입
• pop_back: 마지막 위치의 요소 삭제

표준 라이브러리에서 vector, deque, list 는 위 조건을 만족합니다. 명시적으로 지정하지 않을 경우, deque가 기본 하위 컨테이너로 선택됩니다.

주요 인터페이스

커스텀 스택 구현 예시

다음 코드는 STL 의 동작 방식을 모방하여 템플릿 기반으로 스택 어댑터를 직접 구현한 예시입니다. 내부 저장소는 기본값으로 deque를 사용하도록 설정되었습니다.

namespace custom_stl
{
    template<typename ValueType, typename Sequence = std::deque<ValueType>>
    class StackAdapter
    {
    public:
        void push(const ValueType& item)
        {
            _storage.push_back(item);
        }

        void pop()
        {
            _storage.pop_back();
        }

        ValueType& top()
        {
            return _storage.back();
        }

        const ValueType& top() const
        {
            return _storage.back();
        }

        size_t size() const
        {
            return _storage.size();
        }

        bool empty() const
        {
            return _storage.empty();
        }

    private:
        Sequence _storage;
    };
}

큐 (Queue) 어댑터

동작 원리 및 정의

큐는 선입선출 (FIFO, First In First Out) 구조를 따릅니다. 요소는 컨테이너의 한 끝 (rear) 에서 삽입되고, 반대쪽 끝 (front) 에서 제거됩니다. 하위 컨테이너는 다음과 같은 연산을 지원해야 합니다.

• empty, size: 상태 확인
• front, back: 양끝 요소 접근
• push_back: 뒤쪽에 요소 삽입
• pop_front: 앞쪽 요소 삭제

deque와 list 가 이 조건을 충족하며, 기본 하위 컨테이너는 deque입니다. vector는 pop_front 연산의 비효율성으로 인해 기본 옵션에서 제외됩니다.

주요 인터페이스

큐 및 우선순위 큐 커스텀 구현

일반적인 큐 어댑터와 더불어, 힙 구조를 기반으로 하는 우선순위 큐 (priority_queue) 의 구현 로직을 포함합니다. 우선순위 큐는 내부적으로 배열 (vector) 을 사용하여 힙 속성을 유지합니다.

namespace custom_stl
{
    // 일반 큐 어댑터 구현
    template<typename ValueType, typename Sequence = std::deque<ValueType>>
    class QueueAdapter
    {
    public:
        void push(const ValueType& item)
        {
            _buffer.push_back(item);
        }

        void pop()
        {
            _buffer.pop_front();
        }

        ValueType& front()
        {
            return _buffer.front();
        }

        const ValueType& front() const
        {
            return _buffer.front();
        }

        ValueType& back()
        {
            return _buffer.back();
        }

        size_t size() const
        {
            return _buffer.size();
        }

        bool empty() const
        {
            return _buffer.empty();
        }

    private:
        Sequence _buffer;
    };

    // 우선순위 큐 구현 (힙 구조 활용)
    template<typename ValueType, typename Sequence = std::vector<ValueType>>
    class PriorityQueueAdapter
    {
    public:
        void push(const ValueType& val)
        {
            _heap.push_back(val);
            sift_up(_heap.size() - 1);
        }

        void pop()
        {
            std::swap(_heap[0], _heap[_heap.size() - 1]);
            _heap.pop_back();
            sift_down(0);
        }

        const ValueType& top() const
        {
            return _heap[0];
        }

        size_t size() const
        {
            return _heap.size();
        }

        bool empty() const
        {
            return _heap.empty();
        }

    private:
        void sift_up(size_t node_idx)
        {
            while (node_idx > 0)
            {
                size_t parent_idx = (node_idx - 1) / 2;
                if (_heap[node_idx] > _heap[parent_idx])
                {
                    std::swap(_heap[node_idx], _heap[parent_idx]);
                    node_idx = parent_idx;
                }
                else
                {
                    break;
                }
            }
        }

        void sift_down(size_t parent_idx)
        {
            size_t child_idx = parent_idx * 2 + 1;
            while (child_idx < _heap.size())
            {
                if (child_idx + 1 < _heap.size() && _heap[child_idx + 1] > _heap[child_idx])
                {
                    ++child_idx;
                }

                if (_heap[child_idx] > _heap[parent_idx])
                {
                    std::swap(_heap[child_idx], _heap[parent_idx]);
                    parent_idx = child_idx;
                    child_idx = parent_idx * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        Sequence _heap;
    };
}