스택과 C++ STL 컨테이너

C++ 컨테이너를 이용한 스택의 구현

• C++의 벡터나 list는 스택이 필요한 모든 기능을 갖추고 있음
• 스택은 데이터의 삽입과 삭제가 한 쪽 끝에서만 일어나는 리스트의 특수한 경우에 지니지 않으므로 당연합니다.
• 따라서 vector 혹은 list를 이용하여 간단히 스택을 구현할 수 있습니다.
• 하나의 자료구조를 구현할 때 다른 자료구조가 제공하는 기능을 그대로 이용하여 구현하는 방식을 보통 delegation(위임)이라고 부릅니다.
• 혹은 이런 방식으로 구현된 클래스를 adapter class라고 부르기도 합니다.

받은 일거리를 직접 하지 않고 넘기는 것을 위임이라고 합니다. 시스템 자체가 실질적으로 자신이 하는 일이 없어 포장지만 갈아끼우면서 실제 일은 다 데이터멤버로 가지고 있는 컨테이너가 제공하는 데이터로 하는 것은 adaptor라고 합니다.

template<typename Cont> 
class Stack {
private:
    Cont c;
    
public:
    typedef typename Cont::value_type value_type;
    
    bool empty() {
        return c.empty();
    }
    
    int size() {
        return c.size();
    }
    
    value_type &top() {
        return c.back();
    }
    
    void push(value_type x) {
        c.push_back(x);
    }

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

int main() {
    Stack<vector<string>> stack1;
    Stack<list<int>> stack2;
    stack1.push("hello");
    stack2.push(100);

    cout << stack1.top() << ' ' << stack2.top() << endl;
    
    if (!stack1.empty())
        stack1.pop();

    return 0;
}

거의 실제적인 내용은 없고 껍데기만 구현하는 식으로 구현하는 것을 adaptor 라고 합니다. 이 stack을 사용할 때 내부적으로 사용할 컨테이너의 타입을 적어주면 됩니다.

 

C++ STL은 이미 stack 컨테이너를 제공하므로 사실 c++에서는 스택을 구현할 필요는 없습니다.

 

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> stack;
    stack.push(21);
    stack.push(22);
    stack.push(24);
    stack.push(25);

    int num = 0;
    stack.push(num);
    stack.pop();
    stack.pop();
    stack.pop();

    while (!stack.empty()) {
        cout << stack.top() << " ";
        stack.pop();
    }

    return 0;
}

 

 

#include <stack>
#include <vector>
#include <list>
#include <iostream>
using namespace std;

int main() {
    stack<char> dsc1; // default는 deque (double-ended queue)

    stack<char, deque<char>> dsc2;

    stack<int, vector<int>> vsil;

    stack<int, list<int>> lsi;

    vector<int> v1{1};

    stack<int, vector<int>> vsi2(v1);
    cout << "The element at the top of stack vsi2 is "
         << vsi2.top() << "." << endl;

    return 0;
}

이렇게 STACK의 내부 또한 지정을 해주고 싶으면 이런식으로 해주면 됩니다. c++ stl에서 stack class에서 default로는 deque를 이용하여 stack을 구현합니다. 

 

character를 저장하는 stack인데 deque<char> 이렇게 구현을 해라 이것이 기본이지만 만약 vector나 list로 지정을 하고 싶다면 stack <int, vector<int>> 이런 식으로 해주시면 되는 것입니다.