알고리즘 - 스택(stack)

스택은 데이터를 임시 저장할 때 사용하는 자료구조로

데이터를 꺼낼 때는 가장 마지막에 넣은 것을 가장 먼저 꺼냅니다.

 

스택에 데이터를 넣는 작업을 Push라 하고, 데이터를 꺼내는 작업을 Pop이라고 합니다.

 

스택

위 그림과 같이 가장 아래쪽을 바텀이라하고 가장 먼저 들어간 데이터입니다.

그리고 가장 위쪽을 탑이라하며 위쪽에 있을 수록 나중에 들어간 데이터입니다.

 

스택도 2개의 파일로 나누어 하겠습니다.

 

---

fixed_stack.py

 

from typing import Any

class FixedStack:
    #고정 길이 스택 클래스

    class Empty(Exception):
        #비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리
        pass

    class Full(Exception):
        # 가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리
        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

 

Empty, Full 클래스는 예외 처리를 위한 클래스입니다.

self.ptr은 데이터의 개수를 나타냅니다. 배열에서 인덱스 + 1을 한 값이라 생각하시면 됩니다.

 

    def push(self, value: Any) -> None:
        # 스택에 데이터를 푸시
        if self.is_full():
            raise FixedStack.Full   # 스택이 가득차 있는지 확인
        self.stk[self.ptr] = value  # 현재 포인터에 데이터를 넣어주고
        self.ptr += 1   # 포인터에 + 1

    def pop(self) -> Any:
        # 스택에서 데이터를 팝(꺼내옴)
        if self.is_empty():
            raise FixedStack.Empty  # 스택이 비어 있는지 확인
        self.ptr -= 1   # 데이터의 개수를 뜻하므로 -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:
        # 스택에서 데이터를 찾아 인덱스를 반환
        for i in range(self.ptr - 1, -1, -1):   # 탑부터 데이터를 찾습니다.
            if self.stk[i] == value:
                return i
        return -1

    def count(self, value: Any) -> bool:
        # 스택에 있는 데이터의 개수를 반환
        c = 0
        for i in range(self.ptr):   
            if self.stk[i] == value:
                c += 1
        return c    # 스택에서 해당 데이터를 찾아 데이터의 개수를 리턴합니다.
    
    def __contains__(self, value: Any) -> bool:
        # 스택에 데이터가 있는지 판단
        return self.count(value)

    def dump(self) -> None:
        # 스택 안의 데이터를 바텀부터 탑 순서로 출력
        if self.is_empty():
            print('스택이 비어있습니다.')
        else:
            print(self.stk[:self.ptr])

 

주석을 확인해주세요.

 

---

fixed_stack_test.py

 

from enum import Enum
from fixed_stack import FixedStack

Menu = Enum('Menu', ['push', 'pop', 'peek', 'find', 'dump', 'clear', 'exit'])


def select_menu() -> Menu:
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep = '   ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)

s = FixedStack(64)

while True:
    print()
    print('ㅡ'*20)
    print(f'현재 데이터 개수: {len(s)} / {s.capacity}')
    menu = select_menu()

    if menu == Menu.push:
        x = int(input('데이터를 입력하세요.: '))
        try:
            s.push(x)
        except FixedStack.Full:
            print('스택이 가득 차 있습니다.')
    
    elif menu == Menu.pop:
        try:
            x = s.pop()
            print(f'팝한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어있습니다.')

    elif menu == Menu.peek:
        try:
            x = s.peek()
            print(f'피크한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어있습니다.')

    elif menu == Menu.find:
        x = int(input('검색할 데이터를 입력하세요.: '))
        if x in s:
            print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
        else:
            print('검색한 값을 찾을 수 없습니다.')

    elif menu == Menu.dump:
        s.dump()

    elif menu == Menu.clear:
        s.clear()

    else:
        break

 

---

결과

 

먼저 데이터를 넣어보겠습니다.

 

push

 

1 -> 12 -> 3 -> 1 -> 5 순서로, 총 5개를 입력했습니다.

dump로 제대로 스택에 들어왔는지 확인해봅시다.

 

dump

 

제대로 저장이 됐습니다.

다음은 find입니다. 1을 찾아봅시다.

 

find

 

현재 스택안에 1이 2개 있기 때문에 2개로 나오고, 위에서부터 찾기 때문에 위치는 인덱스 3으로 나옵니다.

 

피크 & 팝

피크를 하면 가장 위에 데이터 5, 팝을 하면 가장 위에 데이터 5가 나옵니다.

그리고 팝을 했기 때문에 5가 스택 안에 없는 것을 볼 수 있습니다.

 

clear

마지막으로 clear를 하면 데이터의 개수가 0 / 64로 바뀌고

dump 했을 때, 스택비 비어있다고 나오는 것을 확인 할 수 있습니다.