deque에 대하여

deque이란 collections 모듈에 속해있으며 단방향 흐름이던 기존 Queue 자료구조와 달리 앞과 뒤(왼쪽과 오른쪽) 양방향에서 삽입 삭제를 할 수 있는 자료구조다.

deque와 Queue, list의 차이

Queue모듈은 멀티 쓰레드 환경을 지원한다. 즉, queue는 멀티 쓰레드 환경에서 thread-safe한 소통을 위해 만들어진 라이브러리이다. 이와 달리 deque는 자료구조의 일종이다. deque는 list와 비슷하게 동작하지만, 그 연산의 복잡도에 있어 deque가 더 빠르게 동작하도록 설계되어 있다고 한다. 또한 deque는 append/pop하는 데에 O(1)의 시간 복잡도가 필요한 데에 반해 list는 O(n)의 시간 복잡도가 필요하다. 따라서 필요에 따라 list가 아닌 deque를 사용하도록 해야겠다.

대표적인 메소드

• append(x): 오른쪽에 x를 추가
• appendleft(x): 왼쪽에 x를 추가
• pop(): 오른쪽 끝에 있는 요소를 삭제하고 반환하며 그 전에 남아있는 요소가 없다면 IndexError 발생
• popleft(): 왼쪽 끝에 있는 요소를 삭제하고 반환하며 그 전에 남아있는 요소가 없다면 IndexError 발생
• extend(iterable argument): 오른 쪽에 요소를 추가한다.