deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.
즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.
데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.
append(x), appendleft(x)
append(x)는 오른쪽 끝에 데이터 x를 추가, appendleft(x)는 왼쪽 끝에 데이터 x를 추가한다.
리스트와 달리 deque는 doubly linked list라 둘의 시간복잡도는 모두 O(1)이다.
pop(), popleft()
pop()은 일반적으로 알고있는 그 pop 연산이 맞다. 즉, stack의 pop처럼 오른쪽 끝의 원소를 pop한다.
popleft()는 맨 왼쪽 item을 pop한다.
마찬가지로 deque는 doubly linked list이므로 둘의 시간복잡도는 O(1)이다.
remove()
- deque.remove(item): item을 데크에서 찾아 삭제한다.