출처: Do it! 자료구조와 함께 배우는 알고리즘 입문- 파이썬편
스택 stack
스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력순서는 후입선출(가장 나중에 넣은 데이터를 가장 먼저 꺼내는) 방식이다.
데이터를 넣는 작업을 푸시push, 데이터를 꺼내는 작업을 팝pop 이라고 한다.
푸시하고 합하는 윗부분을 top, 아랫부분을 bottom이라고 한다.
스택 구현
- 스택 배열: stk -> 푸시한 데이터를 저장하는 list형 배열, 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]
- 스택 크기: capacity -> 스택의 최대 크기를 나타내는 int형 정수, len(stk)로 나타냄
- 스택 포인터 : ptr -> 스택에 쌓여있는 데이터의 갯수를 나타내는 정수값, 스택이 비어있으면 ptr은 0, 가득차 있으면 capacity와 같은 값이다.
- 예외 처리 클래스: empty -> pop() 또는 peek()를 호출할 때 스택이 비어있으면 내보내는 예외 처리
- 예외 처리 클래스: full -> push() 함수를 호출할 때 스택이 가득차 있으면 내보내는 예외 처리
- 초기화 __init__() 함수 -> 스택배열을 생성하는 준비작업을 수행함. 원소수가 capacity이고 모든 원소가 None인 리스트형 stk 생성. 스택이 비어있으므로 스택 포인터 ptr의 값 0으로 지정
- 쌓여있는 데이터의 갯수를 알아내는 __len__() 함수 -> 데이터의 개수 반환 , 여기서는 스택 포인터 ptr값 그대로 반환
- 스택이 비어있는지를 판단하는 is_empty() 함수 -> 스택이 비어있으면 True, 아니면 False
- 스택이 가득차 있는지를 판단하는 is_full() 함수 -> 더이상 푸시할 수 없는 상태, 가득차 있으면 True, 그렇지 않으면 False 반환
from typing import Any
class FixedStack:
#고정 길이 스택 클래스
class Empty(Exception): # 비어있는 fixedStack에 팝 또는 피크 할 때 내보내는 예외 처리
pass
class Full(Exception): #가득찬 FixedStack에 푸시할 때 내보내는 예외 처리
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 >= capacity # 스택이 가득차 있는지 판단
push() 함수
스택에 데이터를 추가함. 스택에 데이터가 가득 차서 더 이상 푸시할 수 없을 때 FixedStack.Full을 통해 예외처리를 한다.
스택이 가득 차 있지 않으면 전달받은 value를 배열을 stk[ptr]에 저장하고, 스택 포인터 ptr을 1 증가시킨다.
def push(self,value:Any)-> None:
#스택에 value 푸시
if self.is_full(): #스택이 가득 차 있는 경우
raise FixedStack.Full #예외 처리 발생
self.stk[self.ptr] = value
self.ptr += 1
pop() 함수
스택의 꼭대기(top)에서 데이터를 꺼내서 반환함. 스택이 비어있는 경우에는 FixedStack.Empty를 통하여 예외처리를 내보냄. 스택이 비어있지 않으면 ptr의 값을 1 감소시키고, stk[ptr]에 저장된 값을 반환함.
def pop(self) -> Any:
#꼭대기에서 데이터 꺼냄
if self.is_empty():
raise FixedStack.Empty
self.ptr -=1
return self.stk[self.ptr]
peek() 함수
스택의 꼭대기 데이터(다음에 pop하는 데이터)를 들여다봄. 스택이 비어있는 경우에는 FixedStack.Empty를 통하여 예외처리를 내보냄. 스택이 비어있지 않으면 꼭대기 원소 stk[ptr-1]의 값 반환. 데이터의 입출력이 없으므로 스택 포인터는 변화하지 않음.
def peek(self)-> Any:
if self.is_empty():
raise FixedStack.Empty
return self.stk[self.ptr-1]
clear() 함수
스택에 쌓여있는 데이터 모두 삭제, 스택 포인터 ptr=0으로 하면된다.
def clear(self) -> None:
self.ptr = 0
find() 함수
스택 본체 배열 stk안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 배열에 어디에 들어있는지를 검색함.
검색은 꼭대기에서 바닥쪽으로 선형검색을 한다. 즉 배열의 인덱스가 큰쪽에서 작은쪽으로 스캔하고, 검색에 실패하면 -1을 반환한다
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() 함수
스택에 쌓여 있는 데이터(value)의 개수를 구하여 반환
def count(self, value:Any) -> int:
c = 0
for i in range(self.ptr):
#바닥쪽 부터 선형 검색
if self.stk[i] == value: # 검색 성공
c+= 1
return c
__contains__() 함수
스택에 데이터가 있는지 판단함. 있으면 True, 없으면 False를 반환함. 예를 들어 스택 s에 x가 포함되어 있는 지 판단은 s.__contains__(x)뿐 아니라 x in s 로 나타낼 수 있음
def __contains__(self, value:Any) -> bool:
#스택에 value가 있는지 판단
return self.count(value) >0
dump() 함수
스택에 쌓여있는 ptr개의 모든 데이터를 바닥부터 꼭대기 까지 순서대로 출력함. 스택이 비어있으면 '스택이 비어있습니다.'를 출력한다.
def dump(self) -> None:
#스택안의 모든 데이터를 바닥부터 꼭대기순으로 출력
if self.is_empty():
print('스택이 비어있씁니다')
else:
print(self.stk[:self.ptr])