Stack

이번 글은 스택에 대해 살펴보도록 하겠습니다.
C++ 코드는 이곳에서 확인할 수 있습니다.

Concept

스택은 LIFO (Last In First Out)을 수행하는 자료구조입니다. 스택은 Push, Pop 메소드를 이용하는 단순한 자료구조입니다. 스택의 동작은 아래 그림과 같으며, 첫째줄이 Push 둘째줄이 Pop 메소드 동작에 대한 그림입니다.

Stack Operation

아래 코드는 스택 메소드에 대한 설명입니다.
Data type을 특정하지 않기 위해서 template과 polymorphism을 위해서 virtual function을 선언했습니다.

template <class Type>
class stackADT
{
public:
    virtual void initializeStack() = 0;
    virtual bool isEmptyStack() const = 0;
    virtual bool isFullStack() const = 0;
    virtual void push(const Type& newItem) = 0; 
    virtual Type top() const = 0;
    virtual void pop() = 0;
};

Push, Pop 메소드 이외에 스택을 사용하는데 사용되는 여러 메소드를 같이 선언해놓았습니다.

template <class Type>
class stackType: public stackADT<Type>
{
public:
    const stackType<Type>
    &operator=(const stackType<Type>&); //Overload the assignment operator.
    void initializeStack();
    bool isEmptyStack() const;
    bool isFullStack() const;
    void push(const Type& newItem);
    Type top() const;
    void pop();
    stackType(int stackSize = 100); //Constructor
    stackType(const stackType<Type>& otherStack); //Copy constructor
    ~stackType(); //Destructor
private:
    int maxStackSize;   //variable to store the maximum stack size 
    int stackTop;       //variable to point to the top of the stack 
    Type *list;         //pointer to the array that holds the stack elements
    void copyStack(const stackType<Type>& otherStack); 
};

스택의 Push에 대한 구현은 아래와 같습니다. 스택 사이즈는 Constructor에서 결정되며, 이 스택에서는 스택의 사이즈를 초기화 이후 재설정하지 못하도록 구현해놓았습니다. 스택이 Full인지 확인한 후, Stack의 Top을 Pointing 하는 member variable을 increment합니다.

template<class Type>
void stackType<Type>::push(const Type& newItem)
{
    if(!isFullStack())
    {
        list[stackTop++] = newItem;
    }
    else std::cout << "Cannot add to a full stack" << std::endl;
}

스택의 Pop에 대한 구현은 아래와 같습니다. 스택이 Empty이면, throw exception이나 Empty print를 수행합니다.

template<class Type>
void stackType<Type>::pop()
{
    if(!isEmptyStack()) stackTop--;
    else                std::cout << "Cannot remove from an empty stack." << std::endl;
}

스택이 가득찬 경우를 위해서 스택을 배열로 구현하면, 기존 스택 사이즈의 기존 스택보다 큰 사이즈로 배열을 새로 할당받아 data copy를 수행하면 됩니다.
이를 스택 메소드로 사용하고자하면, 다음과 같이하면 됩니다. 기존 스택 사이즈와 동일한 사이즈의 배열을 할당받은 뒤, (Pop 기존 스택 -> Push 같은 사이즈의 스택)을 끝내고 (Pop 같은 사으즈의 스택 -> 더 큰 사이즈의 스택) 순서로 수행하면 됩니다.

기타 문의사항을 댓글로 남겨주시면 감사하겠습니다.