템플릿·스택·큐

이 Part에서 다루는 것

• 템플릿이 “중복 제거”를 넘어 “타입 안전한 재사용”을 만드는 방식
• 함수/클래스 템플릿, 특수화, 인스턴스화 시점의 핵심 개념
• 스택/큐의 추상화(ADT)와 벡터/리스트 기반 구현 선택 기준
• 원형 큐의 인덱스 규칙과 자주 나는 버그 포인트

학습 목표

• 템플릿 코드가 언제 실제 함수/클래스로 생성되는지 설명할 수 있다.
• 스택과 큐를 인터페이스 중심으로 구현하고 복잡도를 예측할 수 있다.
• 원형 큐의 front/back/size 불변식을 코드로 안전하게 유지할 수 있다.

---

템플릿 문법

함수 템플릿: 타입별 코드 생성을 자동화

template<typename T>
void Print(const T& value)
{
    std::cout << value << '\n';
}

• T는 “나중에 결정되는 타입 매개변수”입니다.
• Print(10), Print(3.14f), Print(std::string("hi"))처럼 호출 타입에 맞춰 인스턴스화됩니다.
• 결과적으로 컴파일러는 각 타입 조합에 맞는 별도 함수를 생성합니다.

클래스 템플릿: 자료구조 재사용의 핵심

template<typename T>
class RandomBox
{
public:
    void Add(const T& value) { _data.push_back(value); }
    const T& Get(int index) const { return _data[index]; }

private:
    std::vector<T> _data;
};

• RandomBox<int>와 RandomBox<float>는 서로 다른 타입입니다.
• 덕분에 컨테이너(Vector<T>, List<T>)를 모든 도메인 타입에 재사용할 수 있습니다.

특수화: 특정 타입만 다르게 처리

template<>
void Print<int>(const int& value)
{
    std::cout << "[int] " << value << '\n';
}

• 전체 로직은 유지하되, 특정 타입에서만 다른 정책이 필요할 때 사용합니다.
• 과도한 특수화는 가독성을 해치므로 “예외 케이스”에만 제한합니다.

템플릿 실전 포인트

• 인스턴스화 시점: 실제로 사용한 타입에서만 컴파일됩니다.
• 숨은 에러: 호출되지 않은 템플릿 코드는 에러가 늦게 드러날 수 있습니다.
• 파일 분리 규칙: 템플릿 구현은 보통 헤더에 둡니다(링커 에러 방지).

---

스택 & 큐

개념 정리

구조	규칙	대표 예시
스택(Stack)	LIFO	Undo, 함수 호출 스택, 팝업 닫기
큐(Queue)	FIFO	작업 대기열, 서버 요청 처리

핵심은 “자료구조 자체”보다 “사용 가능한 연산을 제한한 인터페이스”입니다.

ADT 인터페이스(의도 강제)

• 스택: push, pop, top, empty, size
• 큐: push, pop, front, back, empty, size
• C++ STL과 동일하게 top/front로 확인하고 pop은 제거만 담당하는 패턴을 권장합니다.

구현 선택 기준

• 스택은 vector 기반이 가장 단순하고 빠릅니다(push_back/pop_back O(1)).
• 큐를 단순 vector로 만들고 앞에서 제거하면 O(N) 이동 비용이 발생합니다.
• 큐는 list 기반 혹은 인덱스 기반 원형 큐가 자연스럽습니다.

벡터 기반 스택 예시

template<typename T>
class Stack
{
public:
    void push(const T& value) { _container.push_back(value); }
    void pop() { _container.pop_back(); }
    T& top() { return _container.back(); }
    const T& top() const { return _container.back(); }
    bool empty() const { return _container.empty(); }
    int size() const { return static_cast<int>(_container.size()); }

private:
    std::vector<T> _container;
};

원형 큐 개념(인덱스 순환)

capacity = 8
front = 읽을 위치
back  = 쓸 위치(다음 삽입 위치)
size  = 현재 원소 개수

다음 인덱스 = (index + 1) % capacity

• front와 back은 배열 끝에 도달하면 0으로 순환합니다.
• 비어 있음: size == 0
• 가득 참: size == capacity

원형 큐 구현 예시(증설 포함)

template<typename T>
class CircularQueue
{
public:
    explicit CircularQueue(int capacity = 8)
        : _data(capacity), _front(0), _back(0), _size(0) {}

    void push(const T& value)
    {
        if (_size == static_cast<int>(_data.size()))
            Grow();

        _data[_back] = value;
        _back = (_back + 1) % static_cast<int>(_data.size());
        ++_size;
    }

    void pop()
    {
        if (empty())
            return;

        _front = (_front + 1) % static_cast<int>(_data.size());
        --_size;
    }

    T& front() { return _data[_front]; }
    const T& front() const { return _data[_front]; }
    bool empty() const { return _size == 0; }
    int size() const { return _size; }

private:
    void Grow()
    {
        std::vector<T> next(_data.size() * 2);
        for (int i = 0; i < _size; ++i)
            next[i] = _data[(_front + i) % static_cast<int>(_data.size())];

        _data.swap(next);
        _front = 0;
        _back = _size;
    }

private:
    std::vector<T> _data;
    int _front;
    int _back;
    int _size;
};

실수 포인트와 결론

• 큐에서 front()/pop() 전에 empty() 확인을 누락하기 쉽습니다.
• 원형 큐 증설 시 “논리적 순서(front부터)”로 복사하지 않으면 순서가 깨집니다.
• 스택/큐는 결국 자료구조를 감싼 의도 표현 도구입니다.

체크 질문 (스스로 답해보기)

• 템플릿 구현을 .cpp로 분리하면 왜 링크 에러가 자주 발생할까?
• 큐를 단순 벡터로 구현할 때 pop_front가 비효율적인 이유는?
• 원형 큐에서 front/back/size 중 하나가 틀리면 어떤 버그가 나는가?

---