[자료구조] 스택 (Stack)

컨테이너 어댑터(Container Adapter)

컨테이너 어댑터는 기존 컨테이너(자료구조)를 기반으로 특정 용도에 맞게 기능을 제한한 것을 말한다. 즉 스택, 큐, 우선순위 큐는 기존 컨테이너인 vector, deque, list 등의 자료구조 위에 특정 규칙(LIFO, FIFO)를 적용한 컨테이너 어댑터이다.

 

 

 

스택 (Stack)

---

스택은 LIFO(Last In First Out, 후입선출) 구조로 가장 마지막에 넣은 데이터가 가장 먼저 나오는 자료구조이다. std::deque 기반의 컨테이너 어댑터로 vector, list 등 다른 컨테이너로도 변경해서 사용 가능하다. 삽입과 삭제, 조회가 항삭 top()에서 이루어지므로 모든 연산의 시간복잡도는 O(1)이다.

멤버함수	설명
push(const T& value)	스택에 데이터 추가
pop()	맨 위 요소 제거 (리턴값 없음)
top()	맨 위 요소 참조 반환
empty()	스택이 비었는지 확인
size()	스택 크기 확인
emplace(args...)	새 요소를 생성 후 스택에 삽입 (C++11)

 

스택 기본 코드

#include <iostream>
#include <stack>

int main() {
    // stack 생성
    std::stack<int> s;

    // push
    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "Top element: " << s.top() << std::endl; // 30

    // pop
    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl; // 20

    // size & empty
    std::cout << "Stack size: " << s.size() << std::endl; // 2
    std::cout << "Is empty? " << (s.empty() ? "Yes" : "No") << std::endl;

    return 0;
}

 

 

 deque를 기반으로 한 stack 구조 (컨테이너 어댑터)

template <class T, class Container = std::deque<T>>
class stack {
protected:
    Container c; // stack이 데이터를 저장하는게 아니라, deque에 위임해서 관리한다.
    
public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

 

 

다른 컨테이너로 stack을 사용하려면?
-> stack 생성시에 템플릿 두번째 인자로 원하는 컨테이너를 넘겨주면 된다.

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

int main() {
    std::stack<int> s1;                       // deque
    std::stack<int, std::vector<int>> s2;     // vector
    std::stack<int, std::list<int>> s3;       // list

    s2.push(1);
    s2.push(2);
    std::cout << s2.top() << std::endl;      // 2
}

 

 

Stack의 활용 사례

• 문자열 짝 검사
• 깊이 우선 탐색(DFS, Depth First, Search)
• Undo/ Redo

 

 

 

---

wooj22 - Overview

양우정