자료 구조(Data Structure)의 스택(Stack) 개념 정리

들어가며

알고리즘 문제를 풀 때 리스트(이하, 배열)로는 해결하기 어려운 경우가 있으며, 이와 같은 상황에서는 스택이나 큐를 사용해야 한다. 따라서, 이번에는 스택에 대해서 공부한 내용을 정리해보았다.

스택

스택(stack)은 '마룬 풀을 쌓은 더미', '겹겹이 쌓음'을 뜻하는 단어로, 데이터가 쌓인 데이터 집합이라고 할 수 있다. 이는 데이터를 임시 저장할 때 사용하는 자료구조이며, 후입선출(LIFO, Last In First Out) 방식으로 데이터를 입/출력할 수 있다. 즉, 데이터를 맨 위에서부터 쌓고, 맨 위에서부터 꺼낸다는 의미이며, 이를 각각 푸쉬(push), 팝(pop)이라고 한다. 예를 들어, 푸쉬와 팝을 간단히 나타내면 다음과 같다.

stack : []
1. push(1) → stack : [1]
2. push(2) → stack : [1, 2]
3. push(3) → stack : [1, 2, 3]
3. pop() → data : 3, stack : [1, 2]

위의 예시와 같이 스택에 데이터가 여러개 쌓여 있는 경우 푸쉬하고 팝하는 마지막 부분을 꼭대기(top)이라고 하고, 쌓여있는 부분(index=0)을 바닥(bottom)이라고 한다.

스택은 상황에 따라 다양하게 구현할 수 있으나, 본 글에서는 고정 길이 스택을 구현하여 스택의 기본 원리를 이해하는데 중점을 두었다. 고정 길이 스택은 일반적으로 스택 본체인 배열, 스택의 크기, 스택에 쌓여있는 데이터의 개수를 나타내는 포인터로 구성되어 있다. 스택에 데이터를 push하거나 pop할 때 스택 포인터로 해당 인덱스를 가리키는 방식으로 수행한다. 즉, 스택 본체 배열의 원소를 직접 삭제할 필요가 없다. 이를 토대로 하여 나타낸 고정 길이 스택의 코드는 다음과 같다.

class FixedStack:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity        # 스택의 크기 초기화
        self.stack = [None] * capacity    # 본체 초기화
        self.pointer = 0                # 포인터 초기화

    def __len__(self) -> int:
        return self.pointer

    def is_null(self) -> bool:
        return self.pointer <= 0

    def is_full(self) -> bool:
        return self.pointer == self.capacity

데이터 푸쉬를 구현하기 전에 스택이 가득 차있는 경우를 먼저 생각해보아야 한다. 이 경우 스택이 가득 차있다고 알려주는 예외 처리를 발생시키도록 한다. 반면, 스택에 공간이 남아있다면 전달받은 값을 stack[pointer]에 저장하고, 포인터를 1만큼 증가시키도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedStack:

    # ..(중략)..

    class Full(Exception):                # 스택이 가득 차있을 때 예외 처리
        pass

    # ..(중략)..

    def push(self, value: any) -> None:
        if self.is_full():
            raise FixedStack.Null       # 예외 처리 발생
        self.stack[self.pointer] = value
        self.pointer += 1

이번에는 데이터 팝을 구현해보자. 마찬가지로 이를 구현하기 전에 스택이 비어있는 경우 스택이 비어있다고 알려주는 예외 처리를 발생시키도록 한다. 반면, 스택이 비어있지 않다면 포인터를 1만큼 감소시키고, stack[pointer]의 값을 반환하도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedStack:

    # ..(중략)..

    class Null(Exception):                # 스택이 비어있을 때 예외 처리
        pass

    # ..(중략)..

    def pop(self) -> any:
        if self.is_null():
            raise FixedStack.Null       # 예외 처리 발생
        self.pointer -= 1
        return self.stack[self.pointer]

이번에는 스택의 데이터를 팝하지 않고도 꼭대기에 위치한 데이터를 확인할 수 있는 픽(peek)을 구현해보자. 팝을 구현할 때와 마찬가지로 스택이 비어있는 경우 예외 처리를 발생시키도록 하고, 스택이 비어있지 않다면 stack[pointer - 1]의 값을 반환하도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedStack:

    # ..(중략)..

    def peek(self) -> any:
        if self.is_null():
            raise FixedStack.Null       # 예외 처리 발생
        return self.stack[self.pointer - 1]

위에서 언급하였듯이 스택에서는 본체 배열의 원소 값을 직접 삭제할 필요가 없다. 따라서, 스택을 비우는 메소드의 코드는 다음과 같이 나타낼 수 있다.

class FixedStack:

    # ..(중략)..

    def clear(self) -> None:
        self.pointer = 0

스택에서 특정 값의 인덱스를 찾아 반환하는 메소드를 살펴보자. 이 경우 스택 본체 배열의 꼭대기(stack[pointer - 1])에서부터 바닥까지 스캔하여 해당 값의 인덱스를 반환해주도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedStack:

    # ..(중략)..

    def find(self, value: any) -> int:
        for i in range(self.pointer - 1, -1, -1):    # 꼭대기부터 선형 검색
            if self.stack[i] == value:
                return i
        return -1

스택에 특정 값이 존재하는지에 대한 유효성 검사를 수행하는 메소드를 살펴보자. 이 경우는 두 가지 방식으로 구현할 수 있다. 첫 번째는 스택 본체 배열의 모든 원소를 스캔하여 해당 값의 개수를 파악하는 방법으로 이를 나타낸 코드는 다음과 같다.

class FixedStack:

    # ..(중략)..

    def count(self, value: any) -> int:
        count = 0
        for i in range(self.pointer):   # 바닥부터 선형 검색
            if self.stack[i] == value:
                count += 1
        return count

    def __contains__(self, value: any) -> bool:
        return bool(self.count(value))

두 번째 방법으로는 멤버십 판단 연산자인 in을 사용하는 방법으로 이를 나타낸 코드는 다음과 같다.

class FixedStack:

    # ..(중략)..

    def __contains__(self, value: any) -> bool:
        return value in self.stack

이렇게 간단하게 파이썬의 리스트로 스택을 구현해보았다. 파이썬의 내장 컨테이너는 리스트, 튜플, 딕셔너리, 집합이 있는데, 그 밖의 여러 컨테이너는 collections 모듈로 제공된다. 특히, namedtuple, deque, ChainMap, Counter, OrderedDict, defaultdict, UserDict, UserList, UserString과 같은 컬렉션이 collections의 주요 컨테이너라고 할 수 있는데, 이 중에서 덱(deque)을 구현하는 deque 컨테이너로도 스택을 구현할 수 있다.

마치며

학교 수업을 통해 스택을 공부할 때, '스택은 후입선출이다'로 큰 틀의 개념만 외웠는데, 직접 구현해보며 동작 원리를 이해하게 되니 스택의 전반적인 개념이 잡혀가는 느낌이다. 다음 글은 스택에 이어서 큐를 공부하고 정리한 내용을 포스팅하겠다.