[Python] deque 사용법

 

deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.(단, 중간 데이터는 제외) 여기선 대표적으로 많이 쓰이는 5가지 operation에 대해 사용법을 정리하려고 한다.

아, 참고로 deque를 사용하려면 import collections.deque를 해주어야 한다.

 

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)이다.

 

첫번째 원소 접근

---

사실 이부분이 좀 헷갈려서 포스팅하면서 정리하려고 했다. 

pop을 하지 않고 맨 처음 원소(가장 왼쪽)를 어떻게 알지? 하는 의문이 들어서 무슨 특별한 연산이 있을 줄 알았는데 그냥 단순히 q[0]을 해주면 된다... ㅎㅎ(허무...)