3.3 스택(Stack) [디딤돌 자료구조와 알고리즘 with C++]

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;

    }

 

    bool Push(int data)

    {

PUSH 연산은 먼저 꽉 찼는지 확인합니다.

        if(IsFull())

        {

만약 꽉 차면 보관할 수 없겠죠.

            return false;

        }

top을 다음 위치로 이동합니다.

        top++;

buffer의 top 인덱스 위치에 data를 보관하세요.

        buffer[top] = data;

        return true;

    }

 

    int Pop()

    {

POP 연산은 먼저 비었는지 확인합니다.

        if(IsEmpty())

        {

여기에서는 0을 반환할게요. 목적에 따라 예외를 던지는 형태로 구현할 수도 있겠죠.

            return 0;

        }

buffer의 top 인덱스 위치에 보관한 값을 반환할 변수에 대입하세요.

        int re = buffer[top];

top 위치를 1 감소합니다.

        top--;

top 위치를 감소하기 전에 기억해 두었던 값을 반환하세요.

        return re;

    }

 

    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;

 

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

 

    return 0;

}

 

▷실행 결과

2, 8, 7, 4

 

 

다음은 앞에서 작성한 스택 코드입니다.

//스택

#include <iostream>

using namespace std;

 

class Stack

{

    int *buffer;

    const int size;

    int top;

public:

    Stack(int size):size(size)

    {

        top = -1;

        buffer = new int[size];

    }

 

    ~Stack()

    {

        delete[] buffer;

    }

 

    bool Push(int data)

    {

        if(IsFull())

        {

            return false;

        }

        top++;

        buffer[top] = data;

        return true;

    }

 

    int Pop()

    {

        if(IsEmpty())

        {

            return 0;

        }

        int re = buffer[top];

        top--;

        return re;

    }

    bool IsFull()

    {

        return (top+1) == size;

    }

 

    bool IsEmpty()

    {

        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;

}

 

스택은 연결리스트를 이용하여 구현할 수도 있어요. PUSH 연산에서 head 뒤에 보관하고 POP 연산에서 head 뒤의 값을 반환하게 구현하면 되겠죠. 또는 PUSH 연산에서 tail 앞에 보관하고 POP, 연산에서 tail 앞의 값을 반환하게 구현할 수도 있어요. 여러분께서는 한 번 작성해 보세요.

 

그런데 스택을 구현하는 것은 개발자에게 큰 의미는 없어요. 개발자에게 필요하는 것은 언제 스택을 사용하는지 판단하고 무엇을 언제 보관하고 언제 꺼내서 어떻게 사용할 것인지를 결정하는 능력이 필요합니다.

 

이 책에서는 동적 프로그래밍에서 스택을 사용하는 알고리즘을 소개하고 구현해 볼 거예요.

 

STL에서는 스택을 템플릿 클래스 stack으로 제공하고 있습니다.

//STL에서 제공하는 stack 사용

#include <iostream>

STL에서 제공하는 스택을 사용하려면 stack 파일을 포함하세요.

#include <stack>

using namespace std;

 

int main()

{

템플릿 클래스이므로 템플릿 형식 인자로 보관할 형식을 나타내야겠죠.

    stack<int> st;//int 형식을 보관하는 스택

 

보관하는 메서드는 push입니다.

    st.push(4); //4

    st.push(7); //4 7

    st.push(8); //4 7 8

    st.push(2); //4 7 8 2

 

비었는지 확인하는 메서드는 empty입니다.

    while(st.empty() == false)

    {

STL에서 제공하는 stack에서는 가장 최근에 보관한 자료를 확인하는 메서드 이름이 top입니다.

        cout<<st.top()<<" ";  //가장 최근에 보관한 자료 확인

그리고 가장 최근에 보관한 자료를 꺼내는 메서드 pop을 제공합니다.

        st.pop();//가장 최근에 보관한 자료 꺼내기

    }

    cout<<endl;

    return 0;

}

 

▷실행 결과

2, 8, 7, 4