데이터를 임시 저장하는 기본 자료구조인 스택에 대해서 알아보자.

스택

스택이란?

데이터를 임시 저장할 때 사용하는 자료 구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 후입선출 방식이다.

push : 스택에 데이터를 넣는 작업
pop : 스택에서 데이터를 꺼내는 작업
top : push와 pop이 일어나는 스택의 제일 윗 부분
bottom : 스택의 제일 아래 부분

스택 구현하기

크기가 결정된 고정 길이 스택을 만들어보자.

스택 배열 : stk
스택의 본체인 list형 배열.
데이터를 푸시하는 경우 stk[0]부터 채워진다.

스택 크기 : capacity
스택의 최대 크기를 나타내는 int형 정수로 배열 stk의 원소 수인 len(stk)와 동일하다.

스택 포인터 : ptr
스택에 쌓여있는 데이터의 개수를 나타내는 정수값으로 스택이 비어있으면 ptr의 값은 0이 되고 가득 차 있으면 capacity와 같은 값이 된다.

예외 처리 클래스 : Empty
pop()함수 또는 peek()함수를 호출 할 때 스택이 비어있으면 내보내는 예외 처리

예외 처리 클래스 : Full
push()함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리

초기화하는 함수 : init()
스택 배열을 생성하는 등의 준비 작업을 수행.
매개변수 capacity로 전달받은 값은 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고 모든 원소가 None인 리스트형 stk를 생성한다. 이때 ptr의 값은 스택이 비어있으므로 0이다.

쌓여 있는 데이터 개수를 알아내는 함수 : len()
스택에 쌓여있는 데이터 개수를 반환 -> 스택 포인터 ptr값을 그대로 반환함

스택이 비어 있는지를 판단하는 함수 : is_empty()
스택이 비어있는지를 판단해 비어있으면 True를, 그렇지 않으면 False를 반환

스택이 가득 차 있는지를 판단하는 함수 : is_full()
스택이 가득 차 있는지를 판단해 스택이 가득 차 있으면 True를, 그렇지 않으면 False를 반환

데이터를 푸시하는 함수 : push()
스택에 데이터를 추가할 때 사용하는 함수.
스택이 가득 차서 더 이상 푸시할 수 없는 경우에는 FixedStack.Full을 통해 예외 처리를 내보낸다.
스택이 가득 차 있지 않으면 전달받은 value를 배열 원소 stk[ptr]에 저장하고 ptr을 1 증가시킨다.

데이터를 팝하는 함수 : pop()
스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환하는 함수.
스택이 비어서 팝할 수 없는 경우에는 FixedStack.Empty를 통하여 예외처리를 내보낸다.
스택이 비어있지 않은 경우 ptr의 값을 1 감소시키고 stk[ptr]에 저장된 값을 반환한다.

데이터를 들여다보는 함수 : peek()
스택의 꼭대기 데이터를 들여다보는 함수.
스택이 비어있는 경우에는 FixedStack.Empty를 통해 예외 처리를 내보낸다.
스택이 비어있지 않으면 꼭대기 원소 stk[ptr]의 값을 반환하고 ptr은 변화하지 않는다.

스택의 모든 데이터를 삭제하는 함수 : clear()
스택을 빈 스택으로 만드는 함수.
ptr의 값을 0으로 변경한다.

raise문을 통한 예외 처리
파이썬에서는 raise문으로 프로그램의 예외 처리를 의도적으로 할 수 있다.

데이터를 검색하는 함수 : find()
스택 본체의 배열 stk 안에 value와 같은 값이 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어 있는지를 검색하는 함수.
스택의 꼭대기에서 바닥까지 선형 검색을 한 뒤, 검색에 성공하면 원소의 인덱스를 반환하고 실패하면 -1을 반환.

데이터 개수를 세는 함수 : count()
스택에 쌓여 있는 데이터의 개수를 구하여 반환.
스택안에 25가 2개 있다면 2를 반환.

데이터가 포함되어 있는지 판단하는 함수 : contains()
스택에 데이터가 있으면 True를 반환, 없으면 False를 반환.

스택의 모든 데이터를 출력하는 함수 : dump()
스택에 쌓여있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력하는 함수.
스택이 비어있으면 '스택이 비어 있습니다'를 출력한다.

고정 길이 스택 FixedStack 클래스를 만들어보자.

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

    def push(self, value: Any) -> None:
        # 스택에 value를 푸시(데이터 넣음)
        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:
        # 스택에서 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 __contain__(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])    

고정 길이 스택 FixedStack 클래스를 사용하여보자

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:
            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로 스택 구현하기

파이썬은 내장 컨테이너 딕셔너리, 리스트, 집합, 튜플 등을 collections 모듈로 제공한다. 이 collections의 deque 모듈을 사용하면 스택을 간단하게 구현할 수 있다.
collection.deque는 맨 앞과 맨 끝 양쪽에서 원소를 추가 및 삭제하는 자료구조인 덱을 구현하는 컨테이너이다. collection.deque와 같은 표준 라이브러리는 프로그램을 간단하게 만들고 동작이 빠르다는 장점이 있지만 코딩테스트에서는 사용이 불가하다...

from typing import Any
from collections import deque

class Stack:
    # 고정 길이 스택 클라스(collections.deque)를 사용

    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:
        # 스택에 value를 푸시
        self.__stk.append(value)

    def pop(self) -> Any:
        # 스택에서 데이터를 팝
        return self.__stk.pop()

    def peek(self) -> Any:
        # 스택에서 데이터를 피크
        return self.__stk[-1]

    def clear(self) -> None:
        # 스택을 비움
        self.__stk.clear()

    def find(self, value: Any) -> Any:
        # 스택에서 value를 찾아 인덱스를 반환하고 찾지 못하면 -1을 반환
        try:
            return self.__stk.index(value)
        except ValueError:
            return -1

    def count(self, value: Any) -> int:
        # 스택에 포함되어 있는 value의 개수를 반환
        return self.__str.count(value)
    
    def __contains__(self, value: Any) -> bool:
        # 스택에 value가 포함되어 있는지 판단
        return self.count(value)

    def dump(self) -> int:
        # 스택 안에 있는 모든 데이터를 나열(바닥에서 꼭대기 순으로 출력)
        print(list(self.__stk))