[Today I Leared 04] 1. 스택

1. 스택이란?

데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식입니다.
push 데이터를 넣는 작업
pop 데이터를 꺼내는 작업
top 푸시하고 팝하는 윗부분
bottom 아랫부분

2. 스택 구현하기

1. 스택 배열 stk
   푸시한 데이터를 저장하는 스택 본체인 list형 배열입니다. 인덱스가 0인 원소를 스택의 바닥이라고 합니다.
2. 스택 크기 capacity
   스택의 최대 크기를 나타내는 int형 정수입니다.
3. 스택 포인터 ptr
   스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값입니다. 스택이 가득 차 있으면 capacity와 같은 값이 됩니다.
4. 예외 처리 클래스 Empty
   pop()함수 또는 peek()함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리입니다.
5. 예외 처리 클래스 Full
   push()함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리입니다.
6. 초기화하는 __init__() 함수
   __init__() 함수는 스택 배열을 생성하는 등의 준비 작업을 수행합니다.
7. 쌓여 있는 데이터 개수를 알아내는 __len__() 함수
   __len__() 함수는 스택에 쌓여 있는 데이터 개수를 반환합니다.
8. 스택이 비어 있는지를 판단하는 is_empty() 함수
   is_empty() 함수는 데이터가 하나도 쌓여 있지 않은 상태, 즉 스택이 비어 있는지 판단합니다.
9. 스택이 가득 차 있는지를 판단하는 is_full()함수
   is_full() 함수는 더 이상 데이터를 푸시할 수 없는 상태, 즉 스택이 가득 차 있는지 판단합니다.
10. 데이터를 푸시하는 push() 함수
    push() 함수는 스택에 데이터를 추가합니다.
11. 데이터를 팝하는 pop() 함수
    pop() 함수는 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환합니다
12. 데이터를 들여다보는 peek() 함수
    peek() 함수는 스택의 꼭대기 데이터(다음에 팝하는 데이터)를 들여다봅니다.
13. 스택의 모든 데이터를 삭제하는 clear() 함수
    clear() 함수는 스택에 쌓여 있는 데이터를 모두 삭제하여 빈 스택을 만듭니다.
14. 데이터를 검색하는 find() 함수
    find() 함수는 스택 본체의 배열 stk 안에 value와 값이 샅은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어 있는지를 검색합니다.
15. 데이터 개수를 세는 count() 함수
    count() 함수는 스택에 쌓여 있는 데이터(value)의 개수를 구하여 반환합니다.
16. 데이터가 포함되어 있는지 판단하는 __contains__() 함수
    __contains__() 함수는 스택에 데이터(value)가 있는지 판단합니다.
17. 스택의 모든 데이터를 출력하는 dump()함수
    dump() 함수는 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력합니다.

class FixedStack:
    """고정 길이 스택 클래스"""
    class Empty(Exception):
        """비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리"""
        pass
    
    class Full(Exception):
        """가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리"""
        pass
    
    def __init__(self, capacity):
        """스택 초기화"""
        self.stk = [None] * capacity # 스택 본체
        self.capacity = capacity # 스택의 크기
        self.ptr = 0 # 스택 포인터
    
    def __len__(self):
        """스택에 쌓여 있는 데이터 개수를 반환"""
        return self.ptr
    
    def is_empty(self):
        return self.ptr <= 0
    
    def is_full(self):
        return self.ptr >= self.capacity
    
    def push(self, value):
        if self.is_full(): # 스택이 가득 차 있는 경우
            raise FixedStack.Full # 예외 처리 발생
        self.stk[self.ptr] = value
        self.ptr += 1
    
    def pop(self):
        """스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
        if self.is_empty(): # 스택이 비어 있는 경우
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]
    
    def peek(self):
        """스택에서 데이터를 피크(꼭대기 데이터를 들여다봄)"""
        if self.is_empty(): # 스택이 비어 있음
            raise FixedStack.Empty
        return self.stk[self.ptr - 1]
    
    def clear(self):
        """스택을 비움(모든 데이터를 삭제)"""
        self.ptr = 0
        
    def find(self, value):
        for i in range(self.ptr - 1, -1, -1): #꼭대기 쪽부터 선형 검색
            if self.stk[i] == value:
                return i # 검색 성공
        return -1 # 검색 실패
    
    def count(self, value):
        """스택에 있는 value의 개수를 반환"""
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c
    
    def __contains__(self, value):
        """스택에 value가 있는지 판단"""
        return self.count(value) > 0
    
    def dump(self):
        """덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])