스택(Stack)이란?
- 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)방식입니다
(LIFO = Last In First Out)
스택에 데이터를 입력하는 작업을 푸시(Push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 합니다.
스택은 일반적으로, 본체로서 lst형 배열을 사용합니다. 이후 해당 배열을 skt으로 부릅니다. 스택의 바닥은 index값이 0이 되겠죠.
스택 크기: capacity는 스택의 초대 크기를 나타내는 int형 정수입니다. 이 값은 stk의 원소 수인 len(stk)과도 일치하죠.
스택 포인터: ptr 은 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 말합니다. 데이터를 push 할때마다 ptr을 이동시켜서 현재 스택에 들어가 있는 데이터 개수를 알 수 있습니다.
아래의 코드는 class 지정을 통해 크기가 고정되어있는 FixedStack을 구현한 코드입니다.
from typing import Any
class FixedStack:
class Empty(Exception):
pass
class Full(Exception):
pass
def __init__(self, capacity:int) -> None:
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: Any):
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: Any):
for i in range(self.ptr-1,-1,-1):
if self.stk[i] == value:
return i
return -1
def count(self, value: Any):
c = 0
for i in range(self.ptr):
if self.stk[i] == value:
c += 1
return c
def __contains__(self, value: Any):
return self.count(value)> 0
def dump(self):
if self.is_empty():
print('스택이 비어 있습니다.')
else:
print(self.stk[:self.ptr])```