스택이란?

Preface

 

이번 장에선 데이터를 담는 방법 중 하나인 스택에 대해 공부했다.

 

스택과 큐는 운영체제를 공부하며 한 번 훑었던 기억이 있어 막히는 부분 없이 쉽게 이해할 수 있었다.

 

또, deque(라이브러리)를 사용하여 코드를 제대로 작성해 본 것은 이번이 처음인데, 길고 복잡한 코드를 짧고 직관적으로 표현할 수 있다는 점이 신기했다.

 

최근 걱정되는 점은 시간 분배에 관한 부분인데, 중간고사 이후 대면 수업이 예정되어 있어 평일에 개발 공부를 어떻게 해야 할 지 고민이다.

 

추가로 다음 주는 시험으로 인해 글을 자주 올리지 못할 것 같다.

---

 

- 스택(stack) : 데이터를 임시 저장할 때 사용하는 자료구조

→ LIFO(Last In First Out) : 후입선출 방식

1) 푸시(push) : 스택에 데이터를 넣는 작업

2) 팝(pop) : 스택에서 데이터를 꺼내는 작업

 

 

- 스택 구현

1) 스택 배열(stk) : 스택 본체인 list 형 배열

2) 스택 크기(capacity) : 스택의 최대 크기를 나타내는 int 형 정수

→ len(stk)와 일치

3) 스택 포인터(ptr) : 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값

 

 

- 스택 코드

from typing import Any


class FixedStack:
    class Empty(Exception):
        pass

    class Full(Exception):
        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

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

    def pop(self) -> Any:
        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:
        for i in range(self.ptr - 1, -1, -1):
            if self.stk[i] == value:
                return i
        return -1

    def count(self, value: Any) -> int:
        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) > 0

    def dump(self) -> None:
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

 

 

- 표준 내장 예외 처리 : 파이썬이 제공하는 예외 처리

→ ValueError, ZeroDivision 등

 

 

- 던더(dunder) : 밑줄 2개(__)인 더블 언더스코어(double underscore)를 줄여서 부르는 말

 

 

- 스택 프로그램 코드

from enum import Enum
from fixed_stack import FixedStack

Menu = Enum('Menu', ['푸시', '팝', '피크', '검색', '덤프', '종료'])


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(f'현재 데이터 개수: {len(s)} / {s.capacity}')
    menu = select_menu()

    if menu == Menu.푸시:
        x = int(input('데이터를 입력하세요.: '))
        try:
            s.push(x)
        except FixedStack.Full:
            print('스택이 가득 차 있습니다.')

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

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

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

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

    else:
        break

 

 

- collections : 파이썬에서 제공하는 내장 컨테이너

→ 표준 라이브러리는 빠른 동작을 기대할 수 있고, 프로그램이 간단하다.

 

 

- deque를 사용한 스택 코드

from typing import Any
from collections import deque


class Stack:
    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:
        self.__stk.append(value)

    def pop(self) -> Any:
        return self.__stk.pop()

    def clear(self) -> None:
        self.__stk.clear()

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

    def count(self, value: Any) -> int:
        return self.__stk.count(value)

    def __contains__(self, value: Any) -> int:
        return self.count(value)

    def dump(self) -> Any:
        print(list(self.__stk))