스택(Stack)
스택이란, Data를 임시 저장할 때 사용하는 자료구조로, 후입선출 방식이다. 데이터를 넣을땐 push, 데이터를 꺼낼땐 pop이라 한다.
스택의 특징을 아래 정리해봤다.
- 스택에는 push하고 pop하는 부분을 꼭데기(top)이라 하고 아랫부분을 바닥(bottom)이라 함
- 인덱스가 0인 원소를 스택의 바닥(bottom)임
- 스택의 최대 크기를 나타내는 capacity 같은 경우 len(stk)와 같음
- 스택 포인터: ptr 은 스택의 개수를 나타낸다. 스택이 비어있으면 0 가득차면 capacity와 같아짐
스택 포인터 응용
예제 : 스택이 비어 있는지 확인해보자
def is_empty(stklist):
return stklist.ptr == 0
이렇게 사용해도 되지만, 프로그램 오류로 인해 ptr 값이 0보다 작아질 수 있어서 아래처럼 작성하면 오류를 최소화 할수 있다
return stklist.ptr <= 0
예제 : 스택이 가득 차 있는지 확인해보자자
def is_full(stklist):
return stklist.ptr == stklist.capacity
이것도 마찬가지로 오류를 방지하기 위해 아래처럼 부등호를 사용하자
return stklist.ptr >= stklist.capacity
음… 책을 읽다가 처음으로 예외 처리에 대해 접했다. 아마 스택에서 오류가 많이 나서 예외 처리 개념을 같이 설명하는것 아닐까 예상해본다. 예외 처리를 하면 실행되다가 중단되는것을 방지할 수 있다. 그리고 original code 에서 error가 발생했을때, 대처하는 코드를 분리할 수 있다는 장점이 있다.
예외(Exception)에 대해 설명하자면, 파이썬이 제공하는 예외처리가 있는데, 표준 내장 예외 처리이다. 표준 내장 예외 처리는 BaseException 클래스와 직간접적으로 파생한 클래스이며, 사용자 정의 예외 처리는 BaseException이 아닌 Exception 클래스이다. 왜냐하면, Eceoption 클래스는 사용자 정의 클래스가 파생하는 것을 전제로 하기 때문이다.
예외 처리
예제 : Empty, pop()함수 또는 peek()함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리리
class Empty(Exception):
"""비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리"""
pass
예제 : Full, push() 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리
class Full(Exceiption):
"""가득 찬 FixedStack에 푸시할 떄 내보내는 예외 처리"""
pass
이제부터는 stack에 사용되는 함수들을 나열하겠다.
스택(Stack) 함수
예제 : init() 함수, 스택 배열을 생성한다. 이때 stack ptr == 0
def __init__(self, capacity):
"""스택 초기화"""
self.stk = [None] * capacity #스택 본체
self.capacity = capacity #스택의 크기
self.ptr = 0 #스택 포인터
예제 : len() 함수, 스택의 쌓여있는 데이터 개수를 반환환
def __len__(self):
return self.ptr
예제 : push() 함수, 스택에 데이터 추가. 스택이 가득차면 FixedStack.Full로 예외처리
def push(self, value: Any) -> None:
"""스택에 value를 푸시"""
if self.is_full(): # 스택이 가득 참
raise FixedStack.Full
self.stk[self.ptr] = value
self.ptr += 1
예제 : pop() 함수, 스택의 top data 반환. 스택이 비었으면 FixedStack.Empty로 예외처리
def pop(self) -> Any:
"""스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
if self.is_empty(): # 스택이 비어 있음
raise FixedStack.Empty
self.ptr -= 1
return self.stk[self.ptr]
예제 : peek() 함수, 스택의 top data 열람. 스택이 비었으면 FixedStack.Empty로 예외처리
def pop(self) -> Any:
"""스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
if self.is_empty(): # 스택이 비어 있음
raise FixedStack.Empty
self.ptr -= 1
return self.stk[self.ptr]
예제 : clear() 함수, 스택의 모든 데이터를 삭제하여 빈 스택으로 만듦. 이때 스택 ptr == 0
def clear(self) -> None:
"""스택을 비움(모든 데이터를 삭제)"""
self.ptr = 0
예제 : find() 함수, 스택에서 데이터를 찾으면 원소의 인덱스를 반환. 실패하면 -1 반환. 만약 중복되는 숫자가 있으면 top에 가까운 원소의 인덱스를 반환한다. 이유는 pop에서 가장 가까우니까
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 # 검색 실패
예제 : count() 함수, 스택에서 특정 data의 개수를 반환. bottom쪽부터 센다.
def count(self, value: Any) -> bool:
"""스택에 포함되어있는 value의 개수를 반환"""
c = 0
for i in range(self.ptr): # 바닥 쪽부터 선형 검색
if self.stk[i] == value:
c += 1 # 들어 있음
return c
예제 : contains() 함수, value가 들어 있는지를 판단
def __contains__(self, value: Any) -> bool:
"""스택에 value가 있는가?"""
return self.count(value)
예제 : dump() 함수, 스택에 쌓여 있는 ptr개의 데이터를 bottom부터 top까지 순차적으로 출력함.
def dump(self) -> None:
"""덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
if self.is_empty(): # 스택이 비어 있음
print('스택이 비어 있습니다.')
else:
print(self.stk[:self.ptr])
마지막 : FixedStack 같은 경우 아래 예시처럼 최대 64개까지를 저장하는 stack을 만들고 싶다면, 아래처럼 명령어를 사용하면 된다
from fixed_stack import FixedStack
s = FixedStack(64)
이렇게 스택의 함수들을 알아보았다. 함수가 어떻게 구성되어 있는지 알아야 추후 사용할때 효율적으로 사용할 수 있을것이다.
