🙋🏻♀️ 스택(Stack)이란?
스택(stack)은 "쌓아놓은 더미"라는 의미로, 데이터를 차곡 차곡 쌓아올린 형태의 자료구조입니다. 때문에 스택은 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 후입선출 (LIFO : Last-In First-Out) 특성을 가지고 있습니다.
즉, 아래의 이미지처럼 입구가 하나인 원통에 공을 모두 집어 넣은 후 그 공들을 다시 뺀다고 생각하면 이해하기 쉽습니다.
🙇🏻♀️ 스택(stack)의 연산
✔︎ create() : 새로운 스택 생성
✔︎ push(n) : 스택에 원소 n을 삽입
✔︎ isEmpty() : 현재 스택이 공백인지 확인
✔︎ isFull() : 현재 스택이 가득차있는지 확인
✔︎ pop() : 스택의 맨 위에 있는 요소 제거
✔︎ peek() : 스택의 맨 위에 있는 요소를 삭제하지 않고 반환
가장 기본이 되는 연산은 삽입 연산(push)과 삭제 연산(pop)입니다.
📍 삽입 연산 : push(n)
스택에 데이터를 저장하기 위해 push 연산이 필요합니다. push는 최근에 저장된 데이터 바로 위에 삽입데이터(n)를 저장하게 됩니다.
스택의 크기보다 데이터를 더 많이 삽입하는 것은 불가능하기에 isFull()연산을 통해 삽입가능 여부를 확인해 보는 것이 가장 좋습니다.
📍 삭제 연산 : pop()
스택에서 데이터를 삭제하기 위해서는 pop()연산이 필요합니다.
pop은 가장 최근에 저장된 데이터부터 순차적으로 삭제하는 구조를 갖게 됩니다.
스택에 데이터가 존재하지 않을 경우에는 pop()연산을 진행할 수 없음을 유의해야합니다.
📚 Python으로 스택(stack) 구현하기
✔︎ 스택(Stack) Class 생성
class Stack:
def __init__(self, max_size = 4) :
self.stack = [] # list 생성
self.top = -1 # top 변수 설정
self.max = max_size - 1 - max_size ▶︎ stack의 크기 (max_size개의 원소를 저장)
- max_size - 1 ▶︎ list의 첫 번째 index는 0부터 시작하기 때문에 -1을 해서 크기를 4로 만들어 주어야 합니다. (0, 1, 2, 3)
- top ▶︎ 스택의 가장 위에 있는 원소의 인덱스를 제공하고 스택에 아무런 데이터가 없을 경우 -1값을 갖습니다.
✔︎ isFull( ) & push( )
def isFull(self) : # push() 연산 전 실행
if self.top == self.max : # 스택이 가득찼을 경우
return True
else :
return False
def push(self, item) :
if self.isFull() == True : # stack이 가득 찬 경우
print("Stack is Full, don't push()") # don't push()
else :
self.stack.append(item) # stack에 item 집어넣기
self.top += 1 # top = top +1- isFull()을 통해 데이터 삽입가능 여부를 확인한 다음 push()연산을 수행하는 것이 바람직합니다.
- item ▶︎ 삽입할 데이터 값
✔︎ isEmpty( ) & pop( )
def isEmpty(self) : # pop() or peek()연산 전 실행
if self.top == -1 : # 스택이 비어있을경우
return True
else :
return False
def pop(self) :
if self.isEmpty() == True : # 스택이 비어있는 경우
print("Stack is Empty. don't pop()") # don't pop()
else :
pop_item = self.stack[self.top] # 제거할 맨 위 요소를 pop_item에 저장
del self.stack[self.top] # 맨 위 요소 삭제
self.top -= 1 # top 위치값을 -1 감소
return pop_item- isEmpty()를 통해 데이터 삭제가능 여부를 확인한 다음 pop()연산을 수행하는 것이 바람직합니다.
✔︎ peek()
def peek(self) :
if self.isEmpty() == True :
print("Stack is Empty. don't peek()")
else: # 스택이 비어있지 않을 경우
return self.stack[self.top] # 스택의 맨 위 요소를 반환- peek()의 경우 맨 위 요소를 삭제하지 않고 반환
🖥️ 전체코드
class Stack:
def __init__(self, max_size = 4) :
self.stack = []
self.top = -1
self.max = max_size - 1
def isEmpty(self) :
if self.top == -1 :
return True
else :
return False
def isFull(self) :
if self.top == self.max :
return True
else :
return False
def push(self, item) :
if self.isFull() == True :
print("Stack is Full, don't push()")
else :
self.stack.append(item)
self.top += 1
def pop(self) :
if self.isEmpty() == True :
print("Stack is Empty. don't pop()")
else :
pop_item = self.stack[self.top]
del self.stack[self.top]
self.top -= 1
return pop_item
def peek(self) :
if self.isEmpty() == True :
print("Stack is Empty. don't peek()")
else:
return self.stack[self.top]