[Python] 스택, 큐 사용하기

스택(Stack)

스택 연산

연산	내용	시간 복잡도
push	스택에 요소 추가	O(1)
pop	스택에 요소 제거	O(1)

 

스택 생성

파이썬에서 리스트로 스택을 사용한다.

stack = []

 

스택의 삽입(push)

stack = [1, 2, 3]
stack.append(4)

 

스택의 제거(pop)

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

 

stack top

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

 

stack empty

if not stack:
	print("empty")

 

큐(Queue)

큐 연산

연산	내용	시간 복잡도
enqueue	큐에 요소 추가	O(1)
dequeue	큐에 요소 제거	O(1)

 

큐 생성

큐는 list가 아닌 collection 모듈의 deque를 사용한다. list를 사용할 경우 구현이 좀 더 복잡해 진다. 스택 처럼 list를 그대로 요소를 앞에 추가하기 때문에 시간 복잡도가 O(N)이 된다.

from collections import deque

# 빈 큐 만들기
queue = deque()

# 원소가 있는 큐 만들기
queue = deque([1, 2, 3])

 

큐 enqueue

queue = deque()
queue.append(3)

 

큐 dequeue

queue = deque([1, 2, 3])

while queue:
    print("pop {}".format(queue.popleft()))