👩🏼‍💻TIL : 8. 스택이란?

1. 스택이란?

스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)방식이다. 스택에 데이터를 넣는 작업을 푸쉬라고 하고, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다. 

 

2. 파이썬으로 고정된 길이 스택을 구현해보자  

 (1) 스택 배열(stk) : 푸쉬한 데이터를 저장하는 스택 본체인 list형 배열이다. 인덱스가 0인 원소를 스택의 바닥이라고 하며, 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]이다.

 

 (2) 스택 크기(capacity) : 스택의 최대 크기를 나타내는 int형 정수이다. 이 값은 배열 stk의 원소 수인 len(stk)와 일치한다.

 

 (3) 스택 포인터(ptr) : 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터(stack pointer)라고 한다.

 

 (4) 스택 포인터의 범위를 지정할 때 주의할 점 : FixedStack 클래스를 사용하여 스택 작업을 수행하는 경우 스택 포인터 ptr 값은 반드시 0 이상이거나 capacity값 이하가 된다. 따라서 is_empty(), is_full() 함수는  <, >= 연산자가 아니라 ==을 사용해서 다음과 같이 정의할 수 도 있다. 하지만 프로그램 오류등으로 값이 0보다 작아지거나 capacity보다 커질 가능성도 있으므로, 부등호로 판단하여 최솟값과 최댓값에 벗어나 접근하는 방법을 막아야 한다. 

 

def is_empty(self) -> bool:
	#스택이 비어있는지 판단
    return self.ptr == 0

def is_full(self) -> bool
	#스택이 가득 차있는지 판단
	return self.ptr == self.capacity

 

from typing import Any

#고정 길이 스택 클래스
class FiexStack:
    
    #비어있는 FixedStack에 팝 또는 피크할 때 내보내는 예외처리
    class Empty(Exception):
        pass
    
    #가득 찬 FixedStack에 팝 또는 피크할 때 내보내는 예외처리
    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 <= 0 
    
    
    #스택이 가득 차있는지 판단
    def is_empty(self) -> bool:
        return self.ptr >= self.capacity
    
    
    #스택에 value를 푸쉬(데이터를 넣음)
    def push(self, value: Any) -> None:
        #스택이 가득 차있는 경우
        if self.is_full():
            #예외처리발생
            raise FiexStack.Full
        self.stk[self.ptr] = value
        self.ptr += 1
        
        
    #스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)    
    def pop(self) -> Any:
        if self.is_empty():
            raise FiexStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]
    
    
    #스택에서 데이터를 피크(꼭대기 데이터를 들여다봄)
    def peek(self) -> Any:
        if self.is_empty():
            raise FiexStack.Empty
        return self.stk[self.ptr - 1]
    
    
    #스택을 비움(모든 데이터를 삭제)
    def clear(self) -> None:
        self.ptr = 0
    

    #스택에서 value를 찾아 인덱스를 반환, 없으면 -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
    
    
    #스택에 value가 있는지 판단
    def count(self, value : Any) -> bool:
        return self.count(value) > 0
    
    
    #덤프 : 스택 안의 모든데이터를 바닥부터 꼭대기 순으로 출력
    def dump(self) -> None:
        if self.is_empty():
            print('스택이 비어있습니다.')
        else : 
            print(self.stk[:self.ptr])

 

 

 (5) 스택 관련 파이썬 함수 

    ① 예외 처리 클래스 Empty

    ② 예외 처리 클래서 Full

    ③ 초기화하는 __init__()

    ④ 쌓여있는 데이터의 개수를 알아내는 __len__()함수

    ⑤ 스택이 비어있는지를 판단하는 is_empty()함수

    ⑥ 스택이 가득 차있는지 판단하는 is_full()함수 

---

0. 번외) 예외 처리의 기본 구조

   ① try문 : 원래 처리

   ② except문 : 예외포착과 처리

   ③ else문 : 예외가 포착되지 않음(생략가능)

   ④ finally문 : 마무리(생략가능)

 

01. 번외) raise문을 통한 예외처리

 ①  파이썬에서는 rasie statement으로 프로그램의 예외처리를 의도적으로 내보낼 수 있음.

 

02.  python3 함수 정의시 

  ①  -> : python3에서는 함수 정의시 나타나는 화살표(->)는 함수 리턴 값의 주석 역할을 한다. 

  ②  : :  이는 매개변수 x 타입에 대 주석이다.