[5.11] 04 스택과 큐

<Do it! 자료구조와 함께 배우는 알고리즘 입문>

04-1 스택이란? 

스택 알아보기

stack : LIFO 후입선출 last in first out 방식의 자료구조

push 데이터 넣기

pop 데이터 꺼내기

top 윗부분

bottom 아랫부분

 

스택 구현하기

스택 배열 stk - 스택 본체 list형 배열

: stk[0] 스택의 buttom

스택 크기 capcity - len(stk)

스택 포인터 : stack pointer - 데이터의 개수를 나타내는 정숫값

cf) from enum import Enum : 열거형 enumeration 지원

 

스택 클래스

- 예외 처리 클래스 Empty

    class Empty(Exception):
        pass

- pop, peek를 할 때 쓰임. 

    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('스택이 비어있습니다.')

- 예외 처리 클래스 Full

- 비슷한 기능으로 push()에서 쓰임

- __init__()

초기화하는 기능임.

매개변수 capacity를 전달받아 리스트 stk 생성

스택의 크기 capacity로 복사

이때 포인터 ptr의 값은 0

    def __init__(self, capacity: int = 256) -> None:
        self.stk = [None] * capacity
        self.capacity = capacity
        self.ptr = 0

- __len__() 함수

쌓여있는 데이터의 개수는? 

    def __len__(self) -> int:
        return self.ptr

- is_empty(), is_full()

__init__()에서 ptr = 0으로 할당함. 따라서 ptr <= 0 일 때 empty

스택의 크기 = capacity이므로 ptr >= capacity일 때 full

    def is_empty(self) -> bool:
        return self.ptr <= 0
    def is_full(self) -> bool:
        return self.ptr >= self.capacity

* cf) 예외처리 기본 구조 try statement

try:

except :

else:

finally: 

- push() 데이터를 푸시

좀아까 정의한 self.is_full()인 경우에는 FixedStack.Full로 예외처리한다. 

그렇지 않은 경우에는

self.stk 리스트의 ptr 포인터 위치에 전달받은 value를 저장하고

포인터를 1 증가시킨다. 

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

- pop()

꺼낼 데이터가 없은 경우 self.is_empty() -> FixedStack.Empty를 불러내어 pass

        except FixedStack.Empty:
            print('스택이 비어있습니다.')

패스한 뒤에는 이렇게 인식해서 출력함. 

원래 작업하려고 다음 위치에 ptr가 설정된 것을 -1 줄인 다음에

그 위치의 리스트값을 반환한다. 

self.stk[self.ptr]

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

- peek()

비어있지 않으면 ptr 값을 수정하지 않은 채로 ptr-1의 리스트값 반환

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

- clear()

 

* cf) raise statement 를 통한 예외처리

표준 내장 예외 처리 ValueError class, ZeroDivisionError class etc..

사용자 정의 예외 처리...

 

- find()

스택에서 value가 들어있는지 검색한다. 포인트값에서 -1까지 -1씩 작아지는 방향으로 찾는다. 

찾지 못하면 -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:Any) -> bool:
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c

- __contains__()

bool 형태(True/False) 출력. 

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

- dump()

비어있지 않으면, stk 전체를 출력한다. 

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

* cf) __len__(), __contains__() 함수

- __len__() : 클래스형의 인스턴스를 전달할 수 있다. obj? ? ? len(obj)

(클래스형의 인스턴스 : 새로 만든 객체 (?))

7.1. 클래스(class)와 인스턴스 - 왕초보를 위한 Python (wikidocs.net)

- __contains__() : x in obj

위키독스

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) -> 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])
    

스택 프로그램

from enum import Enum
from class_making 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) #capacity 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