[자료구조] Deque(덱)(Python)

* 개요

Deque(덱)은 단뱡향으로만 데이터의 삽입 / 삭제가 가능했던 큐와는 달리 양방향으로 데이터의 삽입 / 삭제가 가능한 자료구조이다. 즉, 스택으로도 쓸 수 있고, 큐로도 쓸 수 있다는 장점이 있다. 리스트 자료형이 있는데, 덱을 많이 사용하는 이유는 리스트보다 덱의 속도가 훨씬 빠르기 때문이다. 리스트는 O(N), 덱은 O(1)의 시간 복잡도를 가진다.

 

* 파이썬으로 구현한 덱

deque 모듈을 활용하여 덱을 구현하였다.

from collections import deque

queue = []
dq = deque(queue)

dq.append(1) # 1 
dq.append(2) # 1 2
dq.append(3) # 1 2 3
dq.appendleft(0) # 0 1 2 3
dq.pop() # 0 1 2
dq.popleft() # 1 2

print(dq)