[자료구조] 스택(Stack) (python 파이썬)

스택(Stack)

스택은 가장 나중에 넣은(push) 데이터를 가장 먼저 꺼내는(pop) 자료구조다.

이런 구조를 Last In First Out(후입선출, LIFO) 또는 First In Last Out(선입후출, FILO)라고 한다.

흔히 택배 트럭에 있는 택배 상자들을 생각하면 된다. 가장 나중에 넣은 택배 상자부터 먼저 꺼내니까

출처: 위키피디아

스택의 연산

- push(): 스택이 가득 찼는지(isFull) 확인하고 가득 차있지 않으면 top 다음 위치에 데이터 삽입.

- pop(): 스택이 비어있는지(isEmpty) 확인하고 비어있지 않으면 top위치에 있는 데이터 return 하고 삭제.

- peek():스택의 top에 있는 데이터 return.

- isFull(): 스택이 가득 찼는지 확인. 스택의 사이즈와 top의 위치가 같다면 return 1. 아니면 return 0.

- isEmpty(): 스택이 비어있는지 확인. top의 위치가 -1이면 return 1. 아니면 return 0. 

스택 in 파이썬

파이썬에서 스택을 사용할 때 따로 라이브러리가 필요 없다. 그냥 리스트에 있는 append랑 pop메서드를 사용하면 된다.

둘 다 시간복잡도는 O(1)이다. 

 

따로 class를 만들어 구현할 수 있지만, 간단하게 list로 구현해 볼 수 있다.

 

예)

stack = [] #빈 리스트 선언

stack.append(2) # push
stack.append(3) # push
stack.append(5) # push

print(stack) # [2, 3, 5]

print(stack.pop()) # 5

print(stack) # [2, 3]

# peek과 같은 기능. top에 있는 요소를 return 한다.
print(stack[-1]) # 3

 

참고

https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm