스택: 차곡차곡 쌓여가고 있는 나의 빨래들처럼

스택이란?

스택은 데이터를 임시로 저장하는 자료구조로 데이터를 차곡차곡 쌓을 수 있습니다. 스택에 데이터를 넣는 작업을 push, 빼는 작업을 pop이라고 합니다. 스택의 윗부분을 top, 아랫부분을 bottom이라고 합니다.

스택 구성요소

스택 배열

스택의 본체입니다. 데이터를 저장하는 공간입니다. 인덱스가 0 인 공간이 바닥(bottom)입니다. 빈 스택에 데이터를 넣으면 인덱스가 0인 공간부터 채워집니다.

stk[0] = data

스택 크기: capacity

스택에 들어갈 수 있는 데이터의 최대 개수입니다. 스택배열의 크기와 일치합니다.

capacity = len(stk)

스택 포인터: ptr

스택이 현재 가진 데이터의 수입니다. ptr이 0이면 스택은 비어있습니다. 스택이 가득찼다면 ptr은 capacity와 같은 값입니다.

ptr = 0 # 스택이 비어있음
ptr = capacity # 스택이 가득 차 있음

스택 구현하기

예외처리, 초기화, 현재 데이터의 수, 스택의 상태(가득찼는지, 비어있는지)

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

from typing import Any

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
        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 # 부등호를 통해 오류 회피

push()

스택에 데이터를 추가하는 함수입니다. 스택이 가득 차 있다면 예외를 발생시킵니다.

def push(self, data: Any) -> None:
    if self.isFull():
        raise FixedStack.Full
    self.stk[ptr] = data
    ptr += 1

pop()

스택에서 데이터를 제거하는 연산입니다. 다만, 주의할 점이 있습니다. 데이터를 제거한다는 것이 반드시 데이터를 즉시 삭제한다는 의미는 아닙니다. 스택은 스택 포인터를 통해 데이터를 관리합니다. 스택 포인터의 범위를 벗어난 데이터는 더 이상 스택이 관리하는 데이터가 아니게 될 뿐입니다. 즉, 스택의 입장에서 제거되는 데이터가 있는 메모리에 새로운 데이터가 들어갈 수 있게 되는 것입니다.

    def pop(self) -> Any:
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]

peek()

스택의 최상단에 있는 데이터를 보여주는 함수입니다.

    def peek(self) -> Any:
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[self.ptr-1]

clear()

스택을 비우는 함수입니다. 스택포인터를 0으로 재설정하는 것으로 구현합니다.

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

find()

스택에서 데이터를 찾는 함수입니다. Top 에서 bottom 방향으로 데이터를 스캔합니다. 데이터가 존재한다면 데이터의 인덱스를, 없다면 -1을 반환합니다.

    def find(self, value:Any) -> Any:
        """스택에서 데이터를 검색"""
        for i in range(self.ptr - 1, -1, -1):
            if self.stk[i] == value:
                return i    # 검색성공
        return -1   # 검색실패

count()

스텍에 특정 데이터의 개수를 반환합니다. 스택의 꼭대기부터 바닥까지 스캔해서 데이터의 존재여부를 확인 후 개수를 셉니다.

    def count(self, value) -> int:
        """특정 데이터의 개수를 반환"""
        count = 0
        for i in  range(self.ptr -1, -1, -1):
            if self.stk[i] == value:
                count += 1
        return count

contains()

스택에 특정 데이터가 있는 지 여부를 판단합니다.

    def __contains__(self, value:Any) -> bool:
        for i in range(self.ptr -1, -1, -1):
            if self.stk[i] == value:
                return True
        return False

dump()

스택의 바닥부터 꼭대기 순으로 모든 데이터를 출력합니다. 스택이 비어있는 경우, ‘비었습니다’를 출력합니다.

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