1. list VS. deque
자료구조의 큐(queue) 특징
- 선입선출(FIFO)
- 단방향
파이썬의 list
- fixed size memory blocks(array)
- 링크드 리스트 (X), 고정된 사이즈의 메모리를 갖는 array (O)
- 따라서, 마지막 원소를 삭제하는 연산은 O(1)의 시간복잡도를 갖지만
- 첫번째 원소 삭제 시 O(n)의 시간복잡도를 가진다
* 첫번째 원소를 삭제하면 삭제 후 남은 모든 원소를 앞으로 이동시키기 때문
파이썬의 deque
- 양방향 큐 (deque: double-ended queue의 줄임말)
- double-linked list로 구현되어 있다
- 큐의 앞, 뒤 양쪽 방향에서 element를 추가하거나 제거할 수 있다
- 그러므로 맨 앞의 element를 삭제해도 시간복잡도는 O(1)이다
- 삽입 삭제 연산 속도가 최적화되어있다
- 양 끝 엘리먼트의 추가(append) 삭제(pop)이 일반적인 리스트보다 빠르다
맨 앞 엘리먼트 삽입 삭제 연산의 시간 복잡도
- 리스트 : O(n)
- deque : O(1)
2. deque 의 쓰임
- 스택처럼 구현해서 사용할 수 있으며
- 큐처럼 구현해서 사용할 수도 있다
- 삽입 삭제 연산이 빈번한 알고리즘에서 리스트보다 속도면에서 월등하다
3. deque 메소드
deque 사용 시 선언 필요!
from colloections import deque
dq = deque()deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.deque.remove(item): item을 데크에서 찾아 삭제한다.deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
* 리스트처럼 insert(), remove(), reverse(), index() 메소드도 사용 가능하다.