다시 말하자면 가장 먼저 들어간 책은 가장 나중에 꺼낼수 있을 것이다. 이런식으로 자료가 가장 밑에 쌓이고(입력), 자료를 가져올때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack 라고 한다. 이러한 Stack 의 특징때문에 흔히 "FILO (First-In-Last-Out)" 혹은 "LIFO (Last-In-First-Out)" 라고 한다. 선입후출, 후입선출 형 자료구조이다.

그림 1. Stack 자료구조

그림 1 은 Stack 자료구조의 모습이다. A 가 가장 먼저 입력된 값이고 E 가 가장 마지막으로 입력된 값이다. 값을 가져올때는 가장 최근에 입력된 데이타인 E 를 가져오게 이다. 만약에 F 라는 새로운 자료를 입력한다면, 가장 윗부분에 쌓이게 될것이다.

Stack 데이타 추상은 자료의 입출력이 LIFO가 되도록 구현하면 된다.

2.1.1절. Stack 구현을 위해 기술되어야할 행동

행동 대신 메서드라고 해도 관계는 없다. Stack 는 LIFO 자료입출력을 위해서 보통 4가지의 메서드가 기술된다. 즉 Push 와 Pop, Empty, Size 이다. 그리고 이외에 stack 사이즈관리 등을 위한 capacity와 같은 몇가지 메서드를 부가적으로 구현할수도 있을것이다. "필수" 라고 되어있는 것은 stack 의 필수 행동들이고 "유용" 이라고 되어 있는것은 구현되면 도움이 되는 행동들이다.

표 1. Stack 기본 행동

Push	stack 의 가장 위(top)에 데이타를 저장한다.	필수
Pop	stack 의 가장위에 있는 데이타를 가져온다. 가져온 데이타는 stack 에서 삭제한다.	필수
Empty	stack 가 비어있는지 확인한다.	필수
Size	스택에 들어있는 원소갯수를 돌려준다.	유용
Capacity	스택의 크기 - 담을수 있는 원소갯수 - 를 구한다.	유용

2.1.2절. 구현 및 테스트

2.1.2.1절. Stack Class

위의 "Stack 기본 행동" 을 모두 구현할수 있도록 클래스를 제작한다. Stack 데이타 추상을 위해서 클래스를 사용하는 이유는 ADT 의 구현이 용이하기 때문이다. 그리고 이번에는 좀더 "일반적인" Stack 데이타 추상을 위해서 Template class 를 이용하도록 하겠다.

stack.h

#include <string>
#include <iostream>

using namespace std;

template <typename T>
class stack
{
    private:
        T *container;    // 저장소 
        int member_num;  // 스택에 저장된 원소의 갯수
        int stack_size;  // 스택의 용량크기
        int ele_sizeof;  // 타입 T 의 sizeof

    public:
        // 생성자 
        // 디폴트 인자로 스택의 용량크기를 받아들인다.  
        // 용량크기 만큼 메모리 할당하고
        // 몇가지 값을 초기화 한다.  
        stack(int asize=12)
        {
            stack_size = asize;
            member_num = 0;
            ele_sizeof = sizeof(T);
            container = (T *)malloc(ele_sizeof * stack_size);
        }

        // 소멸자
        // 스택을 free 한다. 
        ~stack()
        {
            free(container);
        }

        // 데이타를 스택에 입력한다.  
        // 만약 스택사이즈가 꽉차있다면 
        // realloc 를 호출해서 스택사이즈를 
        // (현재 스택사이즈 * 2) 만큼 늘려준다.
        void push_back(T data)
        {
            if (member_num == (stack_size - 1))
            {
                stack_size *= 2;
                container = (T *)realloc(container, ele_sizeof * stack_size);
            }
            *(container + member_num) = data;
            member_num++;
        }

        // 스택에서 데이타를 꺼낸다.  
        T pop_back()
        {
            member_num --;
            return *(container+member_num);
        }

        // 데이타가 비어있는지 확인한다. 
        bool empty()
        {
            return member_num == 0;
        }

        // 스택에 저장된 데이타의 갯수 
        int size()
        {
            return member_num;
        }

        // 스택의 용량
        int capacity()
        {
            return stack_size;
        }
};

쏘쓰는 간단함으로 설명하지 않겠다.

다음은 템플릿 클래스로 구현한 stack 자료추상의 구현이 잘되었는지 확인하기 위해서 만든 main() 함수를 포함한 테스트용 코드이다.

stack_test.cc

#include "stack.h"
#include <iostream>
using namespace std;
int main()
{
    stack<int> mystack(2);
    int i, size;

    cout << "Capacity " << mystack.capacity()<< endl;
    mystack.push_back(1);
    mystack.push_back(2);
    mystack.push_back(3);
    mystack.push_back(4);
    cout << "Capacity " << mystack.capacity()<< endl;

    cout << "size : " << mystack.size() << endl;

    size = mystack.size();
    for (i  = 0; i < size; i++)
    {
        cout << mystack.pop_back() << endl;
    }

    if (mystack.empty())
    {
        cout << "stack is empty" << endl;
    }
}

위의 코드는 쓸만하게 작동하지만 string, vector 과 같은 자료형은 값으로 사용할수 없도록되어있다. 이들은 malloc() 함수를 이용해서 메모리 할당이 가능하지 않기 때문이다. 이럴경우 malloc 대신 new 를 사용하면 될것인데, 이것은 각자 코딩해보기 바란다.

Cache Error