[python] stack 구현 (고정길이 스택 fixed stack, class 활용)

(본 포스팅은 Do It! 시리즈의 '자료구조와 함께 배우는 알고리즘 입문 - 파이썬편'을 참고하여 작성하였습니다.)

 

데이터를 임시 저장하는 기본 자료 구조는 대표적으로 두 가지가 있는데, 스택(stack)과 큐(queue)이다.

 

스택은 일반적으로 데이터 입력과 출력 순서가 후입선출(Last in First Out)인 것이 특징이다.

이미지 출처: holdycoders

이 기능을 구현하기 위해서 우리가 생각해봐야할 부분은 어떤 것이 있을까?

 

크게 살펴보자면

 

첫째로, 데이터를 집어 넣는 push 기능

둘째로, 데이터를 꺼내는 pop 기능

셋째로, 스택의 길이를 알려주는 len 기능

넷째로, 스택이 비었는지 확인하는 기능

다섯번 째로, 스택이 가득 차 있는지 확인하는 기능

여섯번 째로, 특정 값이 스택 어디에 위치해있는지 확인하는 기능

일곱번 째로, 특정 값이 스택에 몇 개나 존재하는지 알려주는 카운트 기능 

여덟번 째로, 스택을 초기화 하는 기능 

마지막으로, 스택의 모든 값을 출력하는 기능 (바닥부터 꼭대기 순)

 

등이 있다.

 

그 외에도 스택을 더 멋들어지게 만들어줄 부가 함수를 추가할 수 있지만, 위 정도의 기능만 구현하고자 한다.

 

아래 코드를 확인해보자. 주석에 유념하며 코드를 살펴보길 바란다

 

 

# 고정 길이 스택 클래스 FixedStack 구현하기

from typing import Any  # 타입 힌트를 위해 typing 모듈로 타입 표시


class FixedStack:
    """고정 길이 스택 클래스"""
    class Empty(Exception):
        """비어 있는 FixedStack에 pop 또는 peek할 때 내보내는 예외처리"""
        pass

    class Full(Exception):
        """가득 찬 FixedStack에 push할 때 내보내는 예외 처리"""
        pass

    def __init__(self, capacity: int=256) -> None:
        """스택 초기화"""
        self.stk = [None] * capacity  # 스택의 본체 - 데이터를 저장하는 스텍 본체인 list형 배열
        self.capacity = capacity      # 스택의 최대 크기를 나타냄
        self.ptr = 0                  # 스택 포인터

    def __len__(self) -> int:
        """스택에 쌓여 있는 데이터 개수 반환"""
        return self.ptr

    def is_empty(self) -> bool:
        """스택이 비어있는지 판단"""
        return self.ptr <= 0  # == 연산자가 아닌 것에 유념

    def is_full(self) -> bool:
        """스택이 가득 차 있는지 판단"""
        return self.ptr >= self.capacity  # == 연산자가 아닌 것에 유념

    def push(self, value: Any) -> None:
        """스택에 value를 push"""
        if self.is_full():
            raise FixedStack.Full
        self.stk[self.ptr] = value
        self.ptr += 1

    def pop(self) -> Any:
        """스택에 value를 pop"""
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]

    def peek(self) -> Any:
        """스택에서 데이터를 피크 (꼭대기에서 데이터를 들여다봄) """
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[self.ptr - 1]

    def clear(self) -> None:
        """스택을 비움 (모든 데이터 삭제)"""
        self.ptr = 0

    def find(self, value: Any) -> Any:
        """스택에서 value를 찾아 인덱스를 반환 (없으면 -1을 반환)"""
        for i in range(self.ptr-1, -1, -1):
            if self.stk[i] == value:
                return i  # 검색 성공
        return -1  # 검색 실패

    def count(self, value: Any) -> int:
        """스택에 있는 value의 개수를 반환"""
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c

    def __contains__(self, value: Any) -> bool:
        """스택에 value가 있는지 판단"""
        return self.count(value) > 0

    def dump(self) -> None:
        """덤프 (스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
        if self.is_empty():
            print('스택이 비어 있습니다')
        else:
            print(self.stk[:self.ptr])