[Data Structure] 템플릿을 이용한 스택 구현

사실 C++에서는 <stack>으로 스택을 사용할 수 있어서 직접 구현할 필요는 없다. 그런데 스택 라이브러리를 사용할 수 없는 일이 발생한다면? 기본적인 구현 방법은 알아야하지 않겠는가. 클래스와 템플릿을 이용하여 구현해보자.

백준의 10828. 스택 문제를 이용하였다.


문제

https://www.acmicpc.net/problem/10828



풀이

스택의 생성부터 각 기능들의 구현들을 차근차근 설명해나가겠다.


1. 스택 선언

template <typename T>
class Stack{
    
    private :
    int Topidx;                 // top의 인덱스
    T* ptr;                     // 저장 공간 설정
    
    
    public :
    Stack(int size);            // 생성자
    ~Stack();                   // 소멸자
    T Pop();                    // stack.pop()
    void Push(const T& val);    // stack.push()
    int Empty();                // stack.empty()
    int Top();                  // stack.top()
    int Size();                 // stack.size()

};

일단 문제에선 int형만 취급하지만, 사실 스택은 어떤 타입이든 저장할 수 있다. 따라서 template로 임의의 타입을 저장할 수 있도록 설정해준다.


2. 스택 생성

template <typename T>
Stack::Stack(int size){
    
    Topidx = -1;                // 배열은 인덱스가 0부터 이므로 -1로 초기 설정
    ptr = new T[size];          // 저장공간 선언
    
};

배열은 index가 0부터 시작하므로 -1로 초기화 해줘야 뒤에 push를 할 때 Topidx++ 연산을 처음부터 적용할 수 있다. 즉 예외처리를 해줄 필요가 없다.


3. 스택 소멸

template <typename T>
Stack::~Stack(){
    
    delete ptr;
    
};

문제와 관계 없지만 구현해보았다.


4. 스택 - push

template <typename T>
void Stack::Push(const T& val){
    
    ptr[++Topidx] = val;        // 생성자에서 -1로 초기설정해 준 이유. 예외 없이 인덱스를 더해줌
    
};

기본적으로 -1부터 시작해야 index 관련 연산을 할 때 예외가 없음


5. 스택 - pop

template <typename T>
T Stack::Pop(){
    
    if(Topidx < 0) return -1;   // Topidx < 0 --> Topidx = -1 --> 스택이 비어있음
    else return ptr[Topidx--];  // 비어있지 않으면 제일 윗부분을 빼고 뺀 정수를 출력
    
};

6. 스택 - empty

template <typename T>
int Stack::Empty(){
    
    if(Topidx < 0) return 1;    // 비어있으면 1
    else return 0;              // 그렇지 않으면 0
    
};

7. 스택 - top

template <typename T>
int Stack::Top(){
    
    if(Topidx < 0) return -1;   // 비어있으면 -1
    else return ptr[Topidx];    // 그렇지 않으면 제일 위의 정수 출력
    
};

8. 스택 - size

template <typename T>
int Stack::Size(){
    
    if(Topidx < 0) return 0;    // 비어있으면 0
    else return Topidx + 1;     // 그렇지 않으면 가장 위의 인덱스 + 1 (예를 들어 인덱스가 0이면 1개인거니까)
    
};

소스코드

//
//  Stack.cpp
//  test
//
//  Created by 신기열 on 09/06/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

template <typename T>
class Stack{
    
    private :
    int Topidx;                 // top의 인덱스
    T* ptr;                     // 저장공간 설정
    
    
    public :
    Stack(int size);            // 생성자
    ~Stack();                   // 소멸자
    T Pop();                    // stack.pop()
    void Push(const T& val);    // stack.push()
    int Empty();                // stack.empty()
    int Top();                  // stack.top()
    int Size();                 // stack.size()

};



template <typename T>
Stack::Stack(int size){
    
    Topidx = -1;                // 배열은 인덱스가 0부터이므로 -1로 초기 설정
    ptr = new T[size];          // 저장공간 선언
    
};



template <typename T>
Stack::~Stack(){
    
    delete ptr;
    
};



template <typename T>
void Stack::Push(const T& val){
    
    ptr[++Topidx] = val;        // 생성자에서 -1로 초기설정해 준 이유. 예외 없이 인덱스를 더해줌
    
};



template <typename T>
T Stack::Pop(){
    
    if(Topidx < 0) return -1;   // Topidx < 0 --> Topidx = -1 --> 스택이 비어있음
    else return ptr[Topidx--];  // 비어있지 않으면 제일 윗부분을 빼고 뺀 정수를 출력
    
};



template <typename T>
int Stack::Empty(){
    
    if(Topidx < 0) return 1;    // 비어있으면 1
    else return 0;              // 그렇지 않으면 0
    
};



template <typename T>
int Stack::Top(){
    
    if(Topidx < 0) return -1;   // 비어있으면 -1
    else return ptr[Topidx];    // 그렇지 않으면 제일 위의 정수 출력
    
};



template <typename T>
int Stack::Size(){
    
    if(Topidx < 0) return 0;    // 비어있으면 0
    else return Topidx + 1;     // 그렇지 않으면 가장 위의 인덱스 + 1 (예를 들어 인덱스가 0이면 1개인거니까)
    
};

int main(){
    
    int n, j = 0;
    cin >> n;
    
    Stack<int> S(10000);
    int stored[10000];
    string s[10001];
    
    for(int i = 0; i < n; i++){
        cin >> s[i];
        if(s[i].compare("push") == 0){
            cin >> stored[j];
            j++;
        }
    }

    j = 0;
    for(int i = 0; i < n; i++){
        if(s[i].compare("top") == 0){
            cout << S.Top() << '\n';
        }
        else if(s[i].compare("empty") == 0){
            cout << S.Empty() << '\n';
        }
        else if(s[i].compare("pop") == 0){
            cout << S.Pop() << '\n';
        }
        else if(s[i].compare("size") == 0){
            cout << S.Size() << '\n';
        }
        else{
            S.Push(stored[j]);
            j++;
        }
    }
}