스택(Stack)

오늘은 stack에 대해 공부해보겠습니다. stack은 나중에 들어온 데이터가 먼저 나오는 Last In First Out 구조입니다.
STL에선 deque로 stack을 대신할 수 있기 때문에 따로 stack이란 라이브러리를 제공하진 않습니다.

Last In First Out(LIFO)

Stack의 대표적인 함수 interface는 다음과 같습니다.

push: 입력된 데이터가 맨 뒤에 추가로 입력이 됩니다.
pop: 맨뒤의 데어터가 삭제됩니다.
top: 맨 나중에 입력된 데이터를 반환합니다.
empty: 데이터가 비워졌는지를 확인하여 true or false를 반환합니다.
full: 데이터가 메모리에 가득 찾는지를 확인하여 true or false를 반환합니다.

다음은 코드를 작성해보겠습니다

#include <iostream>
using namespace std;
template <typename T>

class stack
{
private:
#define MAX_SIZE 8
    T dataArray[MAX_SIZE];
    int _top;
public:
    stack() : _top(0)
    {
        memset(dataArray, 0, sizeof(dataArray));
    }

    ~stack() {}

    void push(T data)
    {
        if (full())
        {
            printf("stack is full\n");
            return;
        }

        dataArray[_top] = data;
        _top++;
    }

    void pop()
    {
        if (empty())
        {
            printf("stack is empty\n");
            return;
        }

        _top--;
    }

    T top()
    {
        return dataArray[_top - 1];
    }

    bool full()
    {
        return _top >= MAX_SIZE;
    }

    bool empty()
    {
        return _top < 0;
    }

    void print()
    {
        for (int k = 0; k < _top; k++)
            printf("%d ", dataArray[k]);
        printf("\n");
    }
};

int main()
{
    stack<int> st;
    st.push(1);
    st.print();

    st.push(2);
    st.print();

    st.push(3);
    st.print();

    cout << "top: " << st.top() << endl;

    st.push(4);
    st.print();

    st.push(5);
    st.print();

    st.pop();
    st.print();
    st.pop();
    st.print();

    return 0;
}

stack이 가득 찾는지 비었는지 확인하려면  _top 인덱스가 메모리의 크기와 비교하면 알 수 있습니다.