알고리즘 - 스택(deque)

collection 모듈의 deque를 사용하면 간단하게 스택을 구현할 수 있습니다.

 

---

stack_deque.py

from typing import Any
from _collections import deque

class Stack:

    class Empty(Exception):
        pass

    class Full(Exception):
        pass

    def __init__(self, maxlen: int = 256) -> None:
        self.capacity = maxlen
        self.stk = deque([], maxlen)

    def __len__(self) -> int:
        return len(self.stk)

    def is_empty(self) -> bool:
        return not self.stk

    def is_full(self) -> bool:
        return len(self.stk) == self.__stk.maxlen

    def push(self, value: Any) -> None:
        if self.is_full():
            raise Stack.Full
        self.stk.append(value)

    def pop(self) -> Any:
        if self.is_empty():
            raise Stack.Empty
        return self.stk.pop()

    def peek(self) -> Any:
        return self.stk[-1]

    def find(self, value) -> Any:
        try:
            return self.stk.index(value)
        except ValueError:
            return -1

    def dump(self) -> int:
        print(list(self.stk))

 

먼저 초기화 부분에 차이가 있습니다.

기존에는 self.stk = [None] * capacity 이렇게 했다면

이번에는  self.stk = deque([], maxlen) 이렇게 해줍니다.

 

그리고 is_empty와 is_full에서 리턴 부분에도 변화가 생겼습니다.

push, pop 부분은 List형을 생각하시면 됩니다.

 

---

stack_deque_test.py

from enum import Enum
from stack_deque import Stack

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


def select_menu():
    s = [f'({m.value}){m.name}' for m in Menu]
    print(*s, sep= '  ')
    n = int(input('메뉴를 선택하세요.: '))
    if 1 <= n <= len(Menu):
        return Menu(n)

s = Stack(16)

while True:
    print(f'스택의 상태: {len(s)} / {s.capacity}')
    menu = select_menu()

    if menu == Menu.push:
        try:
            x = int(input('추가 할 값을 입력하세요.: '))
            s.push(x)
            print('추가 완료\n')
        except Stack.Full:
            print('스택에 자리가 없습니다.\n')

    elif menu == Menu.pop:
        try:
            pop = s.pop()
            print(f'팝한 값은 {pop}입니다.\n')
        except Stack.Empty:
            print('스택이 비어있습니다.\n')

    elif menu == Menu.peek:
        print(f'가장 위에 값은 {s.peek()}입니다.\n')

    elif menu == Menu.find:
        x = int(input('찾을 값을 입력하세요.: '))
        find = s.find(x)
        if find == -1:
            print('찾는 값이 스택 안에 없습니다.\n')
        else:
            print(f'{x}는 {find} 위치에 있습니다.\n')

    elif menu == Menu.dump:
        s.dump()
        print('\n')

    else:
        break

 

위 파일은 FixedStack 부분과 차이가 없어서 넘어가겠습니다.

 

---

결과

 

결과 화면