[Python] collections.deque - 큐 시간초과 방지하기, 덱

from collections import deque

deque = deque(배열)

deque.append(원소) : 오른쪽에 삽입
deque.appendleft(원소) : 왼쪽에 삽입

deque.popleft() : 왼쪽 pop
deque.pop() : 오른쪽 pop

deque.clear() : 삭제
deque.insert(i, 원소) : i번째에 원소 삽입

list()보다는 확실히!! 빠른것을 확인할 수 있다. 

 

list도 append, pop, len 다 O(1)이어서 괜찮을 줄 알았는데...😢

* list는 끝 원소의 pop만 O(1)이고 pop(0)은 O(N)이라고 한다 *

 

[시간복잡도] 

https://wiki.python.org/moin/TimeComplexity

 

https://j-ungry.tistory.com/189

deque : double-ended queue