deque는 양방향 큐이다. 보통 큐(Queue)와 스택(Stack)과는 다르게 deque는 앞뒤 양쪽으로 데이터를 추가하거나 제거할 수 있다. 다시 말해, 입력 값을 앞쪽으로 나올 수도 들어갈 수도 있고, 뒤쪽으로 들어갈 수도 나올 수도 있는 자료구조이다.
다음 4가지 method를 이용하여 데이터를 입력하고 제거할 수 있다.
from colletctions import deque
d= deque()
- d.append(x) : list와 동일하게 오른쪽으로 새로운 데이터를 입력한다.
- d.appendleft(x) : 왼쪽으로 새로운 데이터를 입력한다.
- d.pop(x) : list와 동일하게 오른쪽에서 원소를 제거한다.
- d.popleft() : 왼쪽에서 새로운 데이터를 입력한다.
그렇다면 deque를 사용하는 이유는 무엇인가? 단순하게 deque를 정의하는 것만으로도 큐와 스택의 구조를 동시에 가질 수 있다는 장점이 있다. 또한 list를 queue로 사용해야 할때, queue대신 deque를 사용하는 것이 시간복잡도에서 우위를 가져온다.
FIFO(First-In,First-Out)구조를 가진 queue는 list에서 데이터를 제거할때 다음의 method를 사용한다
queue.pop(0)
리스트에서 list.pop()은 O(1)의 시간복잡도를, list.pop(i)은 O(N)의 시간 복잡도를 가져온다. pop(i)를 사용하게 되면 list의 메모리를 재할당해야 하는 경우들이 생겨서, 연산시간이 오래 걸릴 수 있다.
반면 list.pop(0)와 같은 성능을 가진 deque.popleft()는 O(1)의 시간복잡도를 가진다.
스택(Stack)의 경우는 list나 deque를 사용해도 상관없지만 Queue로 사용해야 할 때는 deque를 사용하는 것이 좋다.( 참고로, deque는 bfs 알고리즘에서 유용하게 쓰인다.)
