Deque("deck"이라고 발음하고 "double-ended queue"의 줄임말이다)는 stack, queue의 역할을 모두 할 수 있는 데이터 스트럭쳐이다. 양쪽에서의 append, pop 연산의 퍼포먼스가 O(1)이라고 한다.
collections — Container datatypes — Python 3.9.4 documentation
collections — Container datatypes Source code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple. namedtuple() factory f
docs.python.org
List 역시 append, pop 연산이 가능하지만, list는 빠른 고정 길이 연산을 위해 최적화되었으며, 기본 데이터 표현의 크기와 위치를 모두 변경하는 pop(0)과 insert(0,v) 연산을 위해 O(n) 메모리 이동 비용이 발생한다.
Deque 사용법
1. deque 선언
from collections import deque
>>> from collections import deque
>>> deq = deque("pizza")
>>> deq
deque(['p', 'i', 'z', 'z', 'a'])
2. append(x), appendleft(x)
>>> deq.append('!')
>>> deq
deque(['p', 'i', 'z', 'z', 'a', '!'])
>>> deq.appendleft('Yum!')
>>> deq
deque(['Yum!', 'p', 'i', 'z', 'z', 'a', '!'])
3. pop(x), popleft(x)
>>> deq.pop()
'!'
>>> deq.popleft()
'Yum!'
>>> deq
deque(['p', 'i', 'z', 'z', 'a'])
4. extend(), extendleft()
extendleft() 같은 경우엔 왼쪽에서 순차적으로 하나씩 들어가기 때문에 이 부분을 주의해야한다.
>>> deq.extend('burger')
>>> deq
deque(['p', 'i', 'z', 'z', 'a', 'b', 'u', 'r', 'g', 'e', 'r'])
>>> deq.extendleft('delicious')
>>> deq
deque(['s', 'u', 'o', 'i', 'c', 'i', 'l', 'e', 'd', 'p', 'i', 'z', 'z', 'a', 'b', 'u', 'r', 'g', 'e', 'r'])
이외에도 더 많은 연산들이 있다.