3.3 스택(Stack) [소스 코드]

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

//스택
#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 앞의 값을 반환하게 구현할 수도 있어요. 여러분께서는 한 번 작성해 보세요.

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

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