Data Structure in C++ - Stack

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다. 

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 세 번째 순서는 스택이다. 

스택은 마지막에 들어간 item이 먼저 나오는 LIFO(Last In First Out) 구조이다. 
비록 이 자료구조는 보통 일상에서 흔히 동작하는 방식이 아닌 다른 방식으로 동작하지만, top 요소 즉, 마지막 요소에 대한 접근을 필요로 할 때 유용하게 사용된다.

또한, Problem Solving을 많이 해본 결과 stack은 여러 문제에서 사용되는데 예를 들어, Tree의 Level 별로 분리하여 탐색을 하는 문제, Parenthesis가 올바르게 되어 있는지에 대한 문제, 후위 연산자 등에서 사용이 자주 된다. 

아래는 스택의 구현이다.

using namespace std;

template <typename T>
class Node
{
public:
    T value;
    Node *next;

    Node(T value)
    {
        this->value = value;
    }
 };

template <typaname T>
class Stack
{
private:
    int size_;
    Node<T> *top_ = nullptr;
public:
    Stack() {
        this->size_ = 0;
    }

    void push(T value) {
        if(this->top_ == nullptr) {
            this->top_ = new Node<T>(value)
        } else {
            Node<T> * tmp = new Node<T>(value);
            tmp->next = this->top_;
            this->top_ = tmp;
        }
        this->size_ += 1;
    }

    void pop() {
        if(this->size_ == 0) {
            cout << "stack is empty" << endl;
        } else {
            Node<T> * tmp = this->top_;
            this->top_ = this->top_->next;
            delete tmp;

            this->size_ -= 1;
        }
    }

    T top(){
        if(this->top_ == nullptr){
            cout << "stack is empty" << endl;
        } else {
            return this->top_->value;
        }
    }

    int size(){
        return this->size_;
    }

    bool IsEmpty(){
        return (this->size_ == 0);
    }
};

알아 두어야 할 것은 Node가 next 포인터만 가지고 있다는 점이다. item을 추가하면 자료구조의 top 정보가 업데이트된다. 
가장 윗 Node를 제거 혹은 값을 가져오는 것을 위한 기능이 각각 구현되어야 한다. 

 

reference : Data Structures in C++ — Part 1. Implementing common data structures in… | by Vijini Mallawaarachchi | Towards Data Science