[자료구조] Stack

자료구조를 사용하는 이유

데이터는 구조화 된 여부에 따라 정형, 비정형으로 구분한다. 컴퓨터 시스템에서 데이터를 효율적으로 다루기 위해서는 데이터가 구조화되어야한다. 데이터를 효율적으로 저장하고 관리하기 위해 구조화 된 형태를 자료구조라고 한다.

 

배열, 스택, 큐 모두 자료구조이다. 자료구조마다 각기 다른 방식으로 데이터를 관리하고 처리한다.

 

스택

개념

스택은 후입선출원칙(LIFO)에 따라 데이터를 관리한다. 데이터를 넣는 순서와 반대로 데이터가 꺼내진다. 즉, 가장 마지막에 넣은 데이터가 가장 먼저 나오게 된다.

스택에서 가장 마지막에 들어간 데이터의 위치를 top이라고 한다.

스택은 push, pop, peek 연산이 있다. push 연산은 데이터를 넣는다. pop은 top에 있는 데이터를 제거한다. peek는 top에 있는 데이터를 보여준다.

구현

전체코드

template <typename T> class Stack {
  public:
    Stack(int capacity = 1) {
        assert(capacity > 0);
        Resize(capacity);
    }

    ~Stack() {
        if (stack_)
            delete[] stack_;
    }

    void Resize(int new_capacity) {
        T *new_stack = new T[new_capacity];
        memcpy(new_stack, stack_, sizeof(T) * Size());
        if (stack_)
            delete[] stack_;
        stack_ = new_stack;
        capacity_ = new_capacity;
    }

    // NOTE: const의 역할
    bool IsEmpty() const {
        if (top_ == -1) {
            return true;
        }
        return false;
    }

    // NOTE: const의 역할
    int Size() const { return top_ + 1; }

    void Print() {
        using namespace std; // NOTE: 해당코드가 함수 내에서도 쓰이네?

        for (int i = 0; i < Size(); i++) // Size() 사용
            cout << stack_[i] << " ";
        cout << endl;
    }

    // Returns TOP element of stack.
    T &Top() const {
        assert(!IsEmpty());

        return stack_[top_];
    }

    // Insert item into the TOP of the stack
    void Push(const T &item) {

        if (top_ + 1 == capacity_) {
            Resize(2 * capacity_);
        }

        stack_[top_ + 1] = item;
        top_ += 1;
    }

    // Delete the TOP element of the stack
    void Pop() {
        assert(!IsEmpty());

        top_ -= 1;
    }

  protected: // 뒤에서 상속해서 사용
    T *stack_ = nullptr;
    int top_ = -1; // 0 아님 - 가장 마지막에 추가 된 원소의 인덱스
    int capacity_ = 0;
};

스택 변수

    T *stack_ = nullptr;
    int top_ = -1; // 0 아님 - 가장 마지막에 추가 된 원소의 인덱스
    int capacity_ = 0;

내부변수로 제네릭을 원소로하는 스택 배열 포인터, top_, capacity_를 정의한다. top_은 가장 최근에 들어온 원소의 인덱스를 추적한다. capacity_는 스택에 담을 수 있는 요소들의 크기를 보여준다.

push

    void Push(const T &item) {

        if (top_ + 1 == capacity_) {
            Resize(2 * capacity_);
        }

        stack_[top_ + 1] = item;
        top_ += 1;
    }

스택이 가득 차 있는 경우에 크기를 재조정한다. 스택에 원소를 넣고 top_을 갱신한다.

pop

    void Pop() {
        assert(!IsEmpty());

        top_ -= 1;
    }

top_을 -1 한다.