스택

🔍 스택이란?

데이터를 수직으로 쌓아 올리고, 가장 위(top)에 있는 요소부터 꺼내는 구조

📌 스택의 특징

• 후입선출(LIFO): 마지막에 들어온 데이터가 가장 먼저 나감
• 데이터 추가(push): top에 쌓음
• 데이터 삭제(pop): top에서 제거
• 예시: Ctrl+Z, 함수 호출 스택, 괄호 검사기 등

---

✨ STL 없이 직접 스택 구현하기

✅ 템플릿 기반 Stack 클래스

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

private:
    Container _container;
};

🔍 설명

• T: 스택에 저장할 데이터 타입
• Container: 내부 자료 저장소 (기본은 vector, list로 변경 가능)
• push: 데이터를 스택의 맨 위에 추가
• pop: 스택의 top 요소 제거
• top: 가장 위에 있는 데이터 반환 (참조로 반환해 성능 향상)
• empty: 스택이 비어있는지 확인
• size: 현재 스택의 요소 개수 반환

---

🧪 실습 예제 (with list 컨테이너)

int main()
{
    Stack<int, list<int>> s;

    s.push(1);
    s.push(2);
    s.push(3);

    while (!s.empty())
    {
        int data = s.top();   // 최상위 원소 확인
        s.pop();              // 최상위 원소 제거
        cout << data << endl;
    }

    int size = s.size(); // 현재 스택 크기 확인
}

💡 결과 출력

3
2
1

마지막에 들어간 3부터 출력 → 후입선출 구조 확인

---

🔁 STL std::stack과 비교

#include <stack>

stack<int> s;
s.push(1);
s.push(2);
s.push(3);

while (!s.empty()) {
    cout << s.top() << endl;
    s.pop();
}

📌 결과는 위에서 구현한 사용자 정의 Stack과 동일합니다.

---

🔄 다양한 컨테이너로 구현 가능!

컨테이너	특징
vector	동적 배열, 빠른 임의 접근, push_back/pop_back에 최적
list	양방향 연결 리스트, 삽입/삭제가 유연함
deque	양쪽 끝 삽입/삭제 가능 (STL stack 기본 컨테이너)

💡 템플릿의 장점: 원하는 컨테이너를 매개변수로 넘겨서 유연한 스택 구조 구현 가능!

---