3.3 스택(Stack)

이번에는 스택을 알아보기로 해요.

스택은 자료를 한쪽으로 보관하고 꺼내는 LIFO(Last In First Out) 방식의 자료구조입니다. 스택에 자료를 보관하는 연산을 PUSH라 말하고 꺼내는 연산을 POP이라고 말합니다. 그리고 가장 최근에 보관한 위치 정보를 TOP 혹은 스택 포인터라 말합니다.

먼저 간단하게 정수를 보관하는 스택을 만들어 보기로 해요.

class Stack
{
    //스택에는 자료를 보관할 저장소가 필요합니다.
    int *buffer;
    //저장소의 크기를 기억하는 멤버를 선언하세요.
    const int size;
    //가장 최근에 보관한 자료의 위치를 인덱스로 기억하는 멤버를 선언하세요.
    int top;
public:
    //생성자는 스택 크기를 입력 인자로 받게 합시다.
    Stack(int size):size(size)
    {

스택의 top은 가장 최근에 보관한 자료의 위치입니다. n개 보관했을 때 가장 최근에 보관한 자료는 인덱스 n-1에 있습니다. 따라서 초기 top은 -1로 설정하세요.

        top = -1;
        //자료를 보관할 저장소를 동적으로 생성하세요.
        buffer = new int[size];
    }

스택을 해제할 때 스택 내부에서 동적 할당한 버퍼를 소멸하세요.

    ~Stack()
    {
        delete[] buffer;
    }

스택에 자료를 보관하는 Push 메서드를 구현합시다.

    bool Push(int data)
    {
        //PUSH 연산은 먼저 꽉 찼는지 확인합니다.
        if(IsFull())
        {
            //만약 꽉 차면 보관할 수 없겠죠.
            return false;
        }
        //top을 다음 위치로 이동합니다.
        top++;
        //buffer의 top 인덱스 위치에 data를 보관하세요.
        buffer[top] = data;
        return true;
    }

스택에서 자료를 꺼내는 Pop 메서드를 구현합시다.

    int Pop()
    {
        //POP 연산은 먼저 비었는지 확인합니다.
        if(IsEmpty())
        {
            //여기에서는 0을 반환할게요. 
            //목적에 따라 예외를 던지는 형태로 구현할 수도 있겠죠.
            return 0;
        }
        //buffer의 top 인덱스 위치에 보관한 값을 반환할 변수에 대입하세요.
        int re = buffer[top];
        //top 위치를 1 감소합니다.
        top--;
        //top 위치를 감소하기 전에 기억해 두었던 값을 반환하세요.
        return re;
    }

꽉 찼는지 확인하는 IsFull 메서드를 구현합시다.

    bool IsFull()
    {
        //스택의 top은 -1이 초기값이므로 top+1이 size와 같을 때 꽉 찬 것입니다.
        return (top+1) == size;
    }
    bool IsEmpty()
    {
        //top이 초기값 -1일 때 빈 것이죠.
        return top == -1;
    }
};

간단히 테스트하는 코드를 작성합시다.

int main()
{
    //간단히 테스트하는 코드를 작성합시다.
    Stack st(10);//크기가 10인 스택

    //다음처럼 스택에 데이터를 보관합시다.
    st.Push(4); //4
    st.Push(7); //4 7
    st.Push(8); //4 7 8
    st.Push(2); //4 7 8 2

    //스택이 비어있지 않다면 값을 꺼내어 출력합시다.
    while(st.IsEmpty() == false)
    {
        cout<<st.Pop()<<" "; 
    }
    cout<<endl; 
    return 0;
}

4, 7, 8, 2 순으로 보관하였으니 꺼내는 순서는 2, 8, 7, 4입니다.

▷실행 결과

2, 8, 7, 4