[알고리즘] 스택이란?

비정확 할 수 있음.

영어의 Stack

Stack의 영어 정의는 쌓다, 쌓아 올린 더미를 뜻한다.

스택의 구조 / 위키 백과

프로그램에서의 Stack

기본적인 자료 구조의 한가지로, 마지막에 집어 넣은 데이터가 먼저 나오는 LIFO(Last In First Out)구조로 저장하는 형식을 말한다. 마지막으로 Push한 값이 Pop해서 나오는 자료 구조이다.

Stack을 구현해 보기

Queue는 Vector를 제한 한 것 이라고도 할 수 있다. 그렇기에 Vector를 제한한 class를 만들어보자.

#include <vector>
using namespace std;

template <typename T>
class Stack
{
public:
    vector<T> vec;

    void push(T v)
    {
        vec.push_back(v);
    }

    T top()
    {
        return vec[vec.size() - 1];
    }

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

    bool empty()
    {
        return vec.empty();
    }

    unsigned int size()
    {
        return vec.size();
    }
};

구현한 Stack을 사용해 보기

잘 나온다.

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    Stack<int> s;

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

    cout << s.top() << "\n"; // 2
    s.pop();
    cout << s.top() << "\n"; // 1
}

관련 문제

백준 Stack