파이썬에서 Stack

Stack

• stack은 후입선출(LIFO)의 자료구조.
• 시간복잡도는 push : O(1), pop : O(1)입니다.
• push와 pop은 모두 stack의 top에 원소를 추가하거나 삭제하는 형식으로 구현됩니다.
• 활용예시는 후위 표시법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로가기), 깊이 우선탐색(DFS)등이 있습니다.

파이썬에서 Stack

파이썬에서는 stack 자료구조를 따로 제공하지 않는다. 따라서 기본 클래스인 list를 활용하여 stack을 흉내내서 사용한다.

 

파이썬에서 list를 활용해 stack 메서드 사용하기

1. stack 선언

그냥 빈 리스트를 선언해주면 된다.

stack = []

2. 원소 추가 : push

list의 append 메서드를 활용해 리스트의 가장 마지막에 원소를 추가한다.

stack = []
stack.append(1)

3. 원소 삭제 : pop

pop 메서드를 활용하여 list의 가장 마지막 원소를 제거한다. pop 메서드는 제거된 원소가 리턴되므로 이를 변수에 담아 사용할 수도 있다.

stack = []
stack.append(1)
top = stack.pop()

4. 맨 위 원소 확인 : top

스택에서 원소를 제거하지 않고 맨 위의 값을 확인(peek) 해야 할 때는 [-1]을 활용해 list의 맨 위값을 확인해주면 된다.

stack = []
stack.append(1)
stack.append(2)
top = stack[-1]

#top == 2
# stack[-1] -> stack[len(stack)-1]과 같음