[C++ STL 만들기] stack 구현

stack은 가장 기본적인 자료구조이다. 이 글에서는 C++의 template를 이용해 어떤 type의 변수던지 사용할 수 있는 STL의 stack을 그대로 구현해보겠다. 구현 방법은 이전 글인 vector만들기와 상당히 유사했다. 코드는 다음과 같다.

#include <iostream>
#include <stdlib.h>
#include <cstring>

using namespace std;

template <typename T>
class mystack {
private:
    int num;
    int len;
    T* tmp;
    T* arr;
public:
    mystack() { //생성자
        mystack::num = 0;
        mystack::arr = (T*)malloc(sizeof(T) * 10); //초기 stack 배열 크기 10으로 설정
        memset(arr, 0, sizeof(arr)); //배열 초기화
        len = 10; //초기 크기 10
        tmp = NULL;
    }

    ~mystack() { //소멸자
        if(arr) free(arr); //메모리 반환
    }

    T top() { //가장 위에 있는 원소 리턴
        return arr[num-1];
    }

    int size() { //stack에 있는 원소의 수 리턴
        return num;
    }

    bool empty() { //stack이 차있는 경우 false 빈 경우 true 리턴
        if(num) return false;
        else return true;
    }

    void pop() { //가장 위에 있는 원소 제거
        if(num == 0) return; //stack이 빈 경우 어떤 일도 일어나지 않음
        arr[num--] = 0; //가장 위에 있느 원소 0으로 설정하고 num 감수
        if(num < len/2) { //만약 배열의 절반도 안차있는 경우
            len /= 2; //배열 크기 절반으로 감소
            tmp = arr; //임시 배열 설정
            arr = (T*)malloc(sizeof(T) * len); //배열 절반 크기로 새로 생성
            for(int i = 0; i < num; i++) arr[i] = tmp[i]; //stack에 있는 원소 복사
            free(tmp); //임시 배열 메모리 반환
        }
    }

    void push(T input) { //원소 stack 맨 위에 추가
        if(num == len - 1) { //stack 배열이 모두 찬 경우
            len *= 2; //배열 크기 두배로 늘림
            tmp = arr; //임시 배열 설정
            arr = (T*)malloc(sizeof(T) * len); //배열 크기 두 배로 생성
            for(int i = 0; i < num; i++) arr[i] = tmp[i]; //stack에 있는 원소 복사
            free(tmp); //임시 배열 메모리 반환
        }
        arr[num++] = input; //원소 맨 위에 추가
    }
};

위의 코드를 이용하여 직접 stack을 실행시켜 보았다.

1부터 4096전까지 2씩  곱하며 stack에 넣었다. 이후 stack의 크기를 출력하였고 그 다음 7개의 원소 top을 출력하고 pop하였다. 그 결과 stack

의 크기를 또 한번 출력하였다. 결과는 다음과 같다.

실제 작동 결과

다음과 같이 12개의 원소가 잘 들어갔고 7개의 원소가 잘 pop된 것을 알 수 있다. template를 사용하였기 때문에 int형 변수 말고도 mystack을 사용할 때 <>안에 다른 자료형을 사용할 수 있다. ADT인 class나 struct도 사용할 수 있기 때문에 굉장히 편리하게 사용할 수 있다. 다른 STL 구현 코드들도 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/C-_Standard_Template_Library

GitHub - Seo-sang/C-_Standard_Template_Library: make C++ STL myself