[자료구조] Stack

LIFO(Last-In First-Out, 후입선출법) 원칙에 따라 element를 삽입/제거하는 자료구조.

말 그대로 가장 늦게 들어간 element가 가장 먼저 뽑혀 나온다. 패스트푸트점에서 컵 반납하는 스프링 통을 생각하면 편할 것이다. 

다음에 포스팅할 Queue와 마찬가지로 자료구조의 한 쪽 끝에서만 삽입/삭제 연산이 이루어지고, 이 최상위 노드의 위치를 가리키는 변수가 있어야 한다. 본 포스팅에서는 이를 'top'이라고 할 것이다.

Stack에 사용되는 연산은 아래와 같다.

1. push(e): element e를 stack의 맨 위에 삽입.

2. pop(): 맨 위의 element를(=가장 늦게 삽입된 element)를 반환하고 제거

3. top() : 맨 위에 element를 '제거하지 않고' 참조

4. isEmpty(): stack이 비었는지 확인

5. size(): stack 내 element 갯수.

해당 연산은 모두 O(1) 시간에 수행 가능하다. 처음에는 size 연산의 경우에 stack 전체를 순회해야 하기 때문에 O(n) 시간이 필요한 것 아닌가 하는 의문이 있었다. 하지만 stack에서는 연산이 이루어질 끝 지점을 지시하는 top 변수가 필요하고, 이 변수의 위치에 따라 해당 stack에 몇 개의 원소가 있는지 알 수 있기 때문에 O(1) 시간에 수행 가능한 것으로 이해하였다.

Array-Based Stack

array를 기반으로 stack을 구현한 것. array는 길이가 고정된 자료구조이기 때문에 array 기반으로 stack을 구현하면 storage 크기가 제한된다는 단점이 있지만 구현이 간편하다.

#include <iostream>
class Custom_stack
{
private:
    int maxSize;
    int top;
    int *stack;

public:
    Custom_stack()
    {
        maxSize = 10000;
        top = -1;
        stack = new int[maxSize];
    }

    void Push(int e)
    {
        if (top >= maxSize)
        {
            std::cout << "FULL STACK\n";
            return;
        }

        stack[++top] = e;
    }

    int Pop(int e)
    {
        if (top == -1)
        {
            std::cout << "Empty Stack\n";
            return -1;
        }

        int result = stack[top--];
        return result;
    }

    int Top()
    {
        if (top == -1)
        {
            std::cout << "Empty Stack\n";
            return -1;
        }

        return stack[top];
    }

    int Size()
    {
        return (top + 1);
    }

    bool IsEmpty()
    {
        if (top==-1)
            return true;
        else
            return false;
    }
};

C++로 간단히 array-based stack을 만들어 봤다.

 

사실 C++ STL에서 제공하는 stack과는 좀 다른데, C++에서 제공하는 stack의 경우 pop연산이 '맨 위의 원소를 반환하고 stack에서 제거' 하는 연산이 아니라 '맨 위의 원소를 제거' 하는 연산이라서, 전자의 의미를 구현하려면 다음과 같이 해야 한다.

int result = stack.top();
stack.pop();

 또, 우리가 흔히 stack을 이해할 때 접시 쌓듯이 이미지를 연상하기 때문에 "맨 위에 있는 element" 라고 표현했지만, 코드에서 볼 수 있듯 실제로는 "맨 끝"에 있다.