[Python 자료구조] Stack(스택) 구현하기

 

오늘은 LIFO 구조인 Stack을 파이썬에서 구현하는 방법에 대해 포스팅하려고 합니다!

스택과 반대로 FIFO 구조인 큐에 대해 알고싶다면 !? 아래 포스팅을 참고해주세요!

[Python 자료구조] Queue (큐) 구현하기

 

 

Stack(스택) ?!

스택은 LIFO(Last - In - First - Out)로써 가장 나중에 들어온 자료가 가장 먼저 꺼내어진다라고 이해하면 쉽습니다.

 

Python에서 Stack 구현하기

Python에서는 기본 클래스인 list를 통해 스택 자료구조를 쉽게 구현할수있습니다.

 

list pop / push 시간복잡도

pop Item	list.pop( )	O(1)
push Item	list.append(item)	O(1)

 

list를 이용하여 Stack 구현하기

stack - Init

list는 파이썬에서 자주 쓰이기 때문에 리스트 자료형 생성은 매우 익숙하실거 같습니다.

stack = [] # []

stack = [1,2,3] # [1,2,3]

 

stack - push

스택에 원소를 넣을 때에는 append 메소드를 이용해 리스트의 가장 마지막에 원소를 넣으실 수 있습니다.

stack = []
stack.append(4) # [4]
stack.append(2) # [4,2]

 

stack - pop

스택에 원소를 제거할 때는 pop 메소드를 이용하여 리스트의 가장 마지막 원소를 제거합니다.

이때 pop메소드에 의해 제거된 원소를 리턴 받습니다.

stack = [1,2,3,4]
top = stack.pop() # stack [1,2,3]

print(top) # 4

 

stack - top

스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하여 찾을 수 있습니다.

stack = [1,2,3,4]
top = stack[-1]# 4 , stack [1,2,3,4]

print(top) # 4

 

 

 

스택을 구현할 수 있는 리스트를 자세하게 알고싶다면!? 아래 포스팅글을 참고해주세요!

리스트(List)