std::stack

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

std::stack

• STL에서 제공하는 스택 컨테이너 어댑터이다.
• 기본적으로 std::deque가 컨테이너로 사용된다.
• 후입선출(LIFO) 구조를 갖는다.
• 순회할 필요가 없으므로 반복자를 제공하지 않는다.
• Top 이외의 원소는 접근할 수 없다.

 

std::stack의 성능

• 모든 연산은 O(1) 시간에 수행된다.

 

#include <iostream>
#include <stack>

using namespace std;

void main()
{
    stack<int> stck;
    
    // 1, 2, 3 Push
    stck.emplace(1);
    stck.emplace(2);
    stck.emplace(3);

    // Pop
    stck.pop();

    cout << "Top: " << stck.top() << endl;

    cout << "Empty: " << boolalpha << stck.empty() << endl;

    cout << "크기: " << stck.size() << endl;
}

 

출력

Top: 2
Empty: false
크기: 2

 

반복자를 이용한 순회가 필요한 경우 std::deque, std::vector, std::list 중 하나를 스택으로 사용해도 된다.

 

#include <iostream>
#include <deque>

using namespace std;

ostream& operator<<(ostream& os, deque<int> deq)
{
    for (int e : deq)
        os << e << ' ';
    
    return os;
}

void main()
{
    deque<int> stck;
    
    // 1, 2, 3 Push
    stck.emplace_back(1);
    stck.emplace_back(2);
    stck.emplace_back(3);

    // Pop
    stck.pop_back();

    cout << stck << endl;

    cout << "Top: " << stck.back() << endl;

    cout << "Empty: " << boolalpha << stck.empty() << endl;

    cout << "크기: " << stck.size() << endl;
}

 

출력

1 2
Top: 2
Empty: false
크기: 2