201218 개발일지(11일차) - 스택과 큐(1) : 오늘은 스택(Stack)

스택이란?

스택은 아래 그림처럼, 가장 마지막에 삽입한 데이터를 가장 먼저 사용하게 되는 자료구조이다.
즉, 후입선출(LIFO=Last-In, First Out)의 특성을 갖는다. 선입후출(FILO)도 같은 의미겠죠?
추가적으로 자동 메모리 및 대부분 네트워크 프로토콜이 이 스택의 개념을 기반으로 구성되어 있다고 한다.

스택의 기능

스택의 중요 기능은 2개다.
1. 데이터 삽입(Push) : 스택의 구조상 최상위(최근)에 저장된다.
2. 데이터 삭제(Pop) : 반대로 최상위(최근)에 데이터를 삭제한다.

그 외의 기능들

주요 기능 외에 다양한 것들을 구현할 수 있다.

1. 스택 배열(stk) : 데이터를 저장하는 스택 본체인 list형 배열
2. 스택 크기(capacity) : 스택의 최대 크기를 나타내는 int형 정수로, stk원소 수인 len(stk)와 일치
3. 스택 포인터(ptr) : 스택에 쌓여있는 데이터 개수를 나타내는 정수값. 비어 있으면 0, 가득 차있으면 capacity와 같음

스택 구현하기

아래의 다양한 함수들로 스택을 만들 수 있다. 코드는 가장 아래 있다.
1. 예외 처리 클래스 Empty 및 Full
2. 초기화하는 __init__() 함수
3. 쌓인 데이터 개수 알아내는 __len__() 함수
4. 스택이 비어 있는지 판단하는 is_empty() 함수
5. 스택이 가득 차 있는지 판단하는 is_full() 함수
6. 데이터 추가하는 push() 함수 : ptr + 1도 수행한다.
7. 데이터를 삭제하는 pop() 함수 : ptr - 1도 수행한다.
8. 가장 최상위(최근) 데이터를 들여보는 peek() 함수
9. 스택 모든 데이터를 삭제하는 clear() 함수
10. 데이터를 검색하는 find() 함수
11. 데이터 개수를 세는 count() 함수
12. 데이터가 포함돼있는지 판단하는 __contains__() 함수
13. 스택의 모든 데이터를 출력하는 dump() 함수

from typing import Any

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

    class Empty(Exception):
        """비어 있는 FixedStack에 pop 또는 peek를 호출할 때 내보내는 예외 처리"""
        pass

    class Full(Exception):
        """가득 찬 FixedStack에 push를 호출할 때 내보내는 예외 처리"""
        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) -> bool:
        """스택에 포함되어있는 value의 개수를 반환"""
        c = 0
        for i in range(self.ptr):  # 바닥 쪽부터 선형 검색
            if self.stk[i] == value:
                c += 1             # 들어 있음
        return c

    def __contains__(self, value: Any) -> bool:
        """스택에 value가 있는가?"""
        return self.count(value)

    def dump(self) -> None:
        """덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
        if self.is_empty():  # 스택이 비어 있음
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])