자료구조: 배열기반 스택(Stack)

잡설

자료구조에 관한 2번째 포스트이다.

이번 포스트에선 스택이란 자료구조에 대해 알아보자

스택이란 무엇인가

여러분 눈 앞에 비어있는 상자가 하나 있다고 생각해보자.

이 상자에다 물건을 담으면 어디서 부터 쌓여나가게 될까. 당연히 바닥에서부터 물건이 차곡차곡 쌓여나갈 것이다.

그럼 이렇게 물건을 담은 상자에서 무언가를 찾을 땐 어떻게 할까? 상자를 부수는게 아니라 뚜껑을 열고 맨 위에서 부터 물건을 하나씩 꺼내면서 자신이 찾는 물건임을 확인할 것이다.

스택도 위의 예시와 마찬가지로 바닥이 막힌 상자에 비유할 수 있다. 먼저 넣은 데이터가 나중에 나오고 나중에 넣은 데이터가 먼저 나오는 First In Last Out(선입후출) 구조를 지니고 있다.

ADT

스택의 ADT를 정의해보자.
스택은 먼저 들어간 자료가 나중에 나온다는 특성을 이용해 넣고, 빼는 push, pop 함수를 정의해준다. 그러나 내가 스택의 맨 윗 부분을 들여다 보고는 싶은데 빼고 싶지는 않을 수도 있다. 그러니 그냥 맨 윗부분의 요소를 들여다 보기만 하는 peek 함수도 정의해 준다.
마지막으로 이 스택이 비어있는지, 가득차있는지 확인하는 is_empty, is_full 함수를 정의해주었다.

그렇게 해서 내가 정의한 스택의 ADT는 아래와 같은 모습이다.

class Stack{
private:
    int * arr;
    int stack_capacity;
    int cursor;
    
public:
    Stack(int size) : stack_capacity(size){
        arr = new int[size];
        cursor = -1;
    }
    
    ~Stack() { delete [] arr; }
    
    void push(int element);
    void pop();
    int peek();
    bool is_empty();
    bool is_full();
};

생성자와 소멸자 정도만 미리 동작을 구현해주었고, 나머지 함수들은 동작이 구현되지 않은 상태이다. 이제 나머지 함수들의 동작을 정의해보자.

스택의 구현

먼저 스택에 요소를 집어넣는 push 함수를 정의해보자.

void Stack::push(int element){
    cousor++
    
    if(is_full()){
        cout << "스택이 꽉 차있습니다" << '\n';
        return;
    }
    
    arr[cursor] = data;
}

이 코드를 한 번 해석해보자.
우선 이 함수를 실행하면 커서를 1 증가시키고, is_full() 함수를 실행해 스택이 꽉 차있는 상태인지 아닌지를 검사한다. 만일 스택이 꽉 차있다면 더 이상 스택에 요소를 집어넣을 수 없기 때문에 함수를 종료해야한다. 그렇기 때문에 스택이 꽉 차있다는 오류 메시지를 띄운 후 그냥 함수를 종료해버린다.

그 다음 맨 윗줄인 ++cursor; 라는 라인을 살펴보자. 왜 시작하자마자 cursor의 값을 1 증가시켜 줬을까?
위에서 스택 클래스의 생성자를 봤다면 알겠지만, cursor를 -1로 초기화를 했기 때문에 우선 스택이 삽입될 배열의 위치를 가리키는 커서를 -1에서 0으로 1 증가시켜 주어야 한다.
파이썬도 아니고 C++에서 arr[-1] 같은 참조를 했다가는 바로 프로그램이 에러를 내뱉을 것이다. 근데 차라리 에러라도 발생시켜 주는게 낫다
그리고, 만일 커서의 값을 증가시키기 전에 is_full 함수를 통해 꽉 차있는지 검사를 하면 실제로는 꽉 찼음에도 불구하고 is_full 함수가 false를 반환해 커서의 값이 배열의 크기를 넘어버리게 되는 문제가 생긴다.

그렇기 때문에 우선 커서를 1 증가시켜 주고 그 다음 is_full 함수를 통해 꽉차있는 상태인지 검사하고, 요소를 삽입해주는 것이다.

이렇게 해주면 마치 통의 꼭대기에다 요소를 넣은 것 같이 작동하게 된다.

다음으로는 pop 함수를 정의해보자

void Stack::pop(){
    if(is_empty()){
        cout << "스택이 비어있습니다" << '\n';
        return;
    }
    
    cursor--;
}

이게 뭔가 싶겠지만, 이게 끝이다.
if(is_empty)) 부분은 이해하기 어렵지 않을 것이라 생각한다. 직관적으로 스택이 비어 있으면 빼낼 것이 없지 않은가?

하지만 cursor-- 부분은 곧바로 이해가 되지 않는 사람도 있을 것이다.
우선 push 함수를 잘 보면 알겠지만 배열기반 스택에선 우선 배열의 참조위치를 나타내는 cursor 변수의 값을 증가시켜 새로운 값을 스택에 넣는 것 처럼 구현했다. 그럼 빼낼 때는 어떨까?
요소를 넣을 떄 단순하게 cursor의 값을 증가시켰으니 뺄 때는 그냥 값을 1 감소시키면 끝이다. 어차피 pop 함수는 특정 값을 리턴하지 않기 때문에 이정도만 하더라도 빼냈다는 행동의 구현에는 충분하다
그럼 그 뒤에 있던 값들은 어떻게 되냐고? 어차피 빼낸 값인데 어떻게 되던지 상관없지 않은가. 그냥 스택에다 새로운 요소를 push하면서 덮어씌워질 것이다. 어차피 논리적으로는 버린 값이기 때문에 별 문제 없다.

다음으로는 스택의 맨 윗부분을 참조하는 peek 함수를 정의해보자

int Stack::peek(){
    if(is_empty()){
        cout << "스택이 비어있습니다" << '\n';
        return INT_MIN;
    }
    return arr[cursor];
}

peek 함수의 구현에는 별 어려움이 없다. 커서가 이미 스택의 맨 윗부분을 가리키고 있으니 커서가 가리키고 있는 배열의 요소를 리턴해주면 끝이다. 만일 스택이 비어있는 상태라면 스택이 비어있다는 오류를 출력해주면 된다.

다음으로 스택이 비어있는지 확인하는 is_empty 함수를 정의해보자

bool Stack::is_empty(){
    return cursor < 0;
}

일단 어떤 경우를 스택이 비어있다고 정의할 수 있을까. 배열에 저장된 요소가 없을 때? 그럼 언제 배열에 저장된 요소가 없다고 할 수 있을까?
일반적으로는 커서가 0을 가리키고 있을 때를 배열에 저장된 요소가 없다고 생각하게 될 것이다. 하지만 여기에는 문제가 있다.
만일 배열 내부에 2개의 요소가 남아있고, 커서는 1을 상태라고 가정하자. 이 상태에서 pop을 진행해서 배열에는 1개의 요소가 남았고, 커서는 0을 가리키게 되었다. 이 상태에서 어떻게 요소가 1개가 남아있는지, 아니면 비어있는지 판단할 수 있을까?
하지만 0을 가리켜도 요소는 있고, 커서가 -1을 가리키고 있을 때 배열이 비어있다고 가정하면 이는 깔끔하게 해결된다.

이제 커서가 -1을 가리키고 있을 때 비어있는 상태라고 결정을 했으니 코드만 짜주면 된다. return cursor < 0은 cursor가 0보다 작은지를 판별해 작으면 true, 아니면 false를 리턴한다.

이로써 is_empty 함수도 정의가 완료되었다.

마지막으로 is_full도 정의해보자

bool Stack::is_empty(){
    return cursor == stack_capacity;
}

가득차있는지 확인하는 방법은 간단하다. 클래스 내부에 이 스택의 최대크기인 stack_capacity가 선언되어 있고 이 변수는 객체의 생성과 함께 초기화 된다. 그리고

자 이제 main 함수를 다음과 같이 선언해주고 잘 작동하는지 체크해보자

int main(int argc, char * argv[]){
    Stack s(5);

    s.push(10);
    s.push(20);
    s.push(30);
    // 10 - 20 - 30
    cout << s.peek() << '\n'; // 30

    s.pop(); // 30
    s.pop(); // 20

    cout << s.peek() << '\n'; // 10

    s.push(100); // OK
    s.push(200); // OK
    s.push(300); // OK
    s.push(400); // OK
    s.push(500); // Stack is full

    cout << s.peek() << '\n'; // 400

    s.pop(); // OK
    s.pop(); // OK
    s.pop(); // OK
    s.pop(); // OK
    s.pop(); // OK
    s.pop(); // Stack is empty
    s.pop(); // Stack is empty

    cout << s.peek() << '\n'; // Stack is empty

    return 0;
}

잘 작동하는 것을 확인할 수 있다.

잡설2

이 포스팅은 배열기반으로 구현한 스택에 대한 포스팅이다.

배열기반 스택은 구현이 간편하고, 속도가 빠르다는 장점이 있지만, 정해진 크기만큼만 쓸 수 있다는 문제점이 존재한다.

다음 포스팅에선 배열이 아니라 연결 리스트를 기반으로한 스택을 구현해보겠다.