스택(stack)은 데이터를 임시 저장할 때 사용하는 자료구조
데이터의 입력과 출력 순서는 후입 선출(LIFO) 방식
LIFO = last in first out
Push : 스택에 데이터를 넣는 작업
Pop : 스택에서 데이터를 꺼내는 작업
Top : 푸시하고 팝하는 윗부분(스택의 꼭대기)
Bottom : 스택의 아랫부분
스택 배열 : stk
푸시한 데이터를 저장하는 스택 본체인 list형 배열
index[0] --> bottom => 표기 : stk[0]
스택 크기 : capacity
사용법 : len(stk)
스택 포인터 : ptr
스택에 쌓여있는 데이터의 개수를 나타내는 정숫값
스택이 비어 있으면 ptr ==0
스택이 가득 차있으면 ptr==len(stk)
스택 중간에 있으면 stk[value]
size : 스택에 들어있는 정수의 개수를 출력
empty : pop() 함수 또는 peek() 함수를 호출할 때 스택이 비어있으면 내보내는 예외처리
Full : push()함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리
__init__() 함수 스택 배열을 생성하는 등의 준비 작업을 수행
매개변수 capacity로 전달받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고 모든 원소가 none인 리스트형 stk를 생성
이때 스택이 비어있으므로 스택 포인터 ptr의 값을 0으로 함
__len__() 함수 스택에 쌓여 있는 데이터 개수를 반환
스택 포인터 ptr 값을 그대로 반환
is_empty() 데이터가 하나도 쌓여 있지 않은 상태, 즉 스택이 비어 있는지 판단 --> 스택이 비어있으면 True, 그렇지 않으면 False를 반환
is_full() 더 이상 데이터를 푸시할 수 없는 상태, 즉 스택이 가득 차 있는지 판단 --> 스택이 가득차 있으면 True, 그렇지 않으면 False 반환
push() 스택에 데이터를 추가
그러나 스택이 가득 차서 더 이상 푸시할 수 없는 경우 FixedStack.Full을 통하여 예외 처리를 내보냄
pop() 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환
스택이 비어서 pop을 할 수 없는 경우에는 FixedStack.Empty 를 통하여 예외 처리를 내보냄
peeek() 스택의 꼭대기 데이터(다음에 pop하는 데이터)를 들여다봄
스택이 비어있으면 FixedStack.Empty를 통하여 예외처리
데이터의 입출력이 없음
clear() 스택을 모두 비움 : ptr의 값을 0으로 함
find() 스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어 있는지를 검색
배열의 인덱스가 큰쪽에서 작은쪽으로 스캔 (top-->bottom)
검색에 성공하면 원소의 인덱스 반환
검색에 실패하면 -1을 반환
count() 스택에 쌓여있는 데이터(value)의 개수를 구하여 반환
__contains__() 스택에 데이터가 있는지 판단. 있으면 True 없으면 False
ex)s.__contains__(x) or x in s
dump() 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기가지 순서대로 출력
from cmath import exp
from typing import Any
class FixedStack:
"""고정 길이 스택 클래스"""
class Empty(Exception):
pass # 비어 있는 fixed stack에 팝 또는 피크할 때 내보내는 예외처리
class Full(Exception):
pass # 가득 찬 fixed stack에 push 할 때 내보내는 예외 처리
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)->int:
return self.ptr<=0
def is_full(self)->bool:
return self.ptr>=self.capacity
def push(self, value:Any)->None:
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:
for i in range(self.ptr -1,-1,-1):
if self.stk[i]==value:
return i
return -1
def count(self, value:Any)->int:
c=0
for i in range(self.ptr):
if self.stk[i]==value:
c+=1
return c
def __contains__(self, value:Any)->bool:
return self.count(value)>0
def dump(self)->None:
if self.is_empty():
print("스택이 비어")
else:
print(self.stk[:self.ptr])