[자료구조] 스택

스택(stack)

- 한쪽 끝(top)에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트

- 후입선출(LIFO, Last-In-First-Out) 리스트

 

시스템 스택

- 프로그램 실행시 함수 호출을 처리

- 프로그램은 함수 호출시 활성 레코드 또는 스택 프레임 구조를 생성하여 시스템 스택의 톱에 둠

• 이전의 스택 프레임에 대한 포인터
• 복귀 주소
• 지역 변수
• 매개 변수

 

- 함수가 자기자신을 호출하는 순환 호출도 같은 방식으로 처리

 

스택 구현

template <class T>
class Stack
{
private:
    T *stack;     // 스택 원소를 위한 배열
    int top;      // top 원소의 위치
    int capacity; // 스택 배열의 크기
public:
    Stack(int stackCapacity = 10);
    // 원소 10개를 담을 수 있는 비어있는 스택 생성

    bool IsEmpty() const;
    // 스택이 비어있으면 true, 그렇지 않으면 false

    T &Top() const;
    // top 원소 리턴

    void Push(const T &item);
    // top에 원소 추가

    void Pop();
    // top 원소 삭제
};

 

스택의 함수 구현

template <class T>
Stack<T>::Stack(int stackCapacity) : capacity(stackCapacity)
{
    if (capacity < 1)
        throw "Stack capacity must be > 0";
    stack = new T[capacity];
    top = -1;
}

template <class T>
inline bool Stack<T>::IsEmpty() const { return top == -1; }

template <class T>
inline T &Stack<T>::Top() const
{ // x를 스택에 더함
    if (IsEmpty())
        throw "Stack is empty";
    return stack[top];
}

template <class T>
void Stack<T>::Push(const T &x)
{
    if (top == capacity - 1)
    {
        ChangeSize1D(stack, capacity, 2 * capacity);
        capacity *= 2;
    }
    stack[++top] = x;
}

template <class T>
void Stack<T>::Pop()
{
    if (IsEmpty())
        throw "Stack is empty. Cannot delete.";
    stack[top--].~T(); // T를 소멸
}