Stack

Stack

 

1. 나중에 들어간 데이터가 제일 먼저 나오는 LIFO(Last In First Out) 구조
2. 특정 위치(한쪽 끝)에서만 데이터를 넣거나 뺼 수 있다.

Stack 연산의 시간복잡도

• 데이터를 추가(push) -> O(1)
• 데이터를 제거(pop) -> O(1)
• 제일 꼭대기의 데이터를 확인(top) -> O(1)

Stack 응용 사례

1. 수식의 괄호 쌍
2. 후위 표기법
3. DFS

Stack 구현

template<class T>
class Stack
{
private:
    int* stack;
    int size, top;
public:
    Stack<T>(int size) : size(size), top(-1)
    {
        stack = new T[size];
    }
    ~Stack<T>()
    {
        delete stack;
    }
    // 데이터 삽입
    bool Push(T data)
    {
        if (top < size - 1)
        {
            top++;
            stack[top] = data;
            return true;
        }
        else
        {
            return false;
        }
    }
    // 데이터 제거
    T Pop()
    {
        if (top >= 0)
        {
            return stack[top--];
        }
        else
        {
            return -1;
        }
    }
    // 맨 위 데이터 반환
    T Top()
    {
        return stack[top];
    }
    // 스택이 비었는지 확인
    bool IsEmpty()
    {
        return top == -1;
    }
};