[자료구조] 스택

Stack

스택은 마지막에 들어온 데이터가 가장 먼저 빠져나가는 데이터 구조이다.
하노이탑이나 팬케이크처럼 아래부터 위로 쌓아가는 구조를 생각하면 된다.
사용 예시로 재귀호출이나 웹 브라우저의 뒤로가기를 들 수 있다.

• Last in First out

ADT

• Push: 요소를 추가한다.
• Pop: 가장 마지막에 추가된 요소를 삭제한다.
• IsEmpty: 스택이 비었으면 True를, 아니면 False를 반환한다.
• Top: 가장 마지막에 추가된 요소를 반환한다.

구현 - C++

template <typename T>
class Stack
{
private:
    T *stack_;
    int top_;
    unsigned int capacity_;

public:
    Stack(int size = 10) : capacity_(size), top_(-1)
    {
        if (size < 1)
            throw "size parameter is less than 1.";

        stack_ = new T[capacity_];
    }
    ~Stack() { delete[] stack_; }

    unsigned int capacity() const { return capacity_; }
    bool IsEmpty() const { return (top_ == -1); }

    T &Top() const
    {
        if (IsEmpty())
            throw "Stack is empty.";

        return stack_[top_];
    }

    void Push(const T &obj)
    {
        if (top_ == capacity_ - 1) // if stack is full...
        {
            T *temp = stack_;
            stack_ = new T[capacity_ * 2]; // double size

            for (int i = 0; i < capacity_; i++) // copy
                stack_[i] = temp[i];

            capacity_ *= 2;
            delete[] temp;
        }
        stack_[++top_] = obj; // add an element
    }

    void Pop()
    {
        if (IsEmpty())
            throw "Stack is empty.";

        stack_[top_--].~T();
    }
};