Python 추상자료형 - 스택 (Stack)

스택이란 ?

차곡차곡 쌓여있는 형태를 말해요.

 

돌이 이렇게 쌓여 있다면

위에 부터 돌을 빼야지 

쓰러지지 않겠죠?

 

새로운 돌을 놓을때도 

맨위에 돌을 놓는 것처럼 

 

파이썬의 추상자료형인 스택도 

돌을 쌓는 것과

마찬가지로 LIFO : Last - in -first-out  형태입니다. 

 

가장 마지막에 들어간 데이터가

가장 먼저 삭제되는 자료형을 말해요.

 

스택의 연산

스택은 다음과 같은 연산이 가능합니다.

 

1. 맨뒤에 데이터를 추가

2. 맨뒤에 데이터를 삭제

3. 맨뒤 데이터에 접근

 

 

파이썬에서 stack 자료구조는 deque를 사용해서 표현 할 수 있어요

from collections import deque

stack = deque()

# 스택에 데이터 추가 
stack.append('1')
stack.append('2')

print(stack)

# 스택에 맨 끝데이터에 접근
print(stack[-1])

# 스텍에 맨 끝 데이터 삭제
print(stack.pop())

print(stack)

 

스택 구현 

동적배열과 링크드 리스트를 이용해서 구현이 가능해요. 

 

시작복잡도는 동적배열이든 더블리 링크드 리스트든

O(1)으로 효율적입니다. 

 

파이썬에서 deque 는 더블리 링크드 리스트로 구현되어있어요. 

참고로 파이썬 리스트는 동적배열로 구현되어있어요.

따라서 파이썬 리스트를 사용하나, deque로 사용하나 시간복잡도의 차이는 없어요.

 

심지어 활용하는 함수도 동일합니다.

stack = []

# 스택에 데이터 추가 
stack.append('1')
stack.append('2')

print(stack)

# 스택에 맨 끝 데이터에 접근
print(stack[-1])

# 스택에 맨 끝 데이터 삭제 
print(stack.pop())
print(stack)