[자료구조] 큐와 덱

Queue는 스택과 상반된 특징을 띄고 있는 자료구조이다. 둘 다 선형 자료구조이지만, 데이터 입출 순서가 달라지는 부분이 있다. 큐에는 데이터를 넣은 순서 그대로 빼게 된다. 첫 번째로 넣은 데이터가 첫 번째로 빠지며 이를 FIFO라 한다. 

큐에 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로 N개의 데이터를 넣고 빼야 한다면 총  O(N)이 될 것이다.

from queue import Queue

q = Queue()
q.put(123)
q.put(456)
q.put(789)
while not q.empty():
	print(q.get())

 

이렇게 import 해서 사용하면 된다. 위 코드에서 대문자 Q로 시작하는 Queue 모듈은 멀티스레딩 환경까지 고려해서 스레드 간에 안전한 방식으로 동작하는 모듈이다. 그래서 이것저것 처리하느라 속도가 느리다.

알고리즘 문제를 풀 때는 멀티스레딩을 고려하며 코드를 작성할 필요가 없기 때문에 굳이 이런 모듈을 사용할 필요가 없다. 따라서 큐 대신 다음과 같이 덱을 사용한다.

 

from collections import deque

dq = deque()
dq.append(123)
dq.append(456)
dq.append(789)
while len(dq):
	print(dq.popleft())

덱(deque)은 Double - Ended Queue의 약자이다. 큐는 항상 넣을 때는 뒤로 넣고 뺄 때는 앞으로만 뺐는데, 덱은 앞뒤 구분없이 어느쪽으로든 넣고 뺄 수 있다. 큐가 할 수 있는 것들은 똑같이 가능하면서 추가 기능들이 있는 셈이니 상위호환이라 볼 수도 있다.