Deque

deque는 deck라고 읽으며 double-ended queue의 줄임말로 양방향으로 append와 pop이 가능한 큐입니다. deque는 thread-safe하며 어떠한 방향으로 append나 pop을 해도 시간 복잡도가 O(1)입니다.

Deque 모듈은 다음과 같이 import하여 사용할 수 있습니다.

1	from collections import deque

Methods

deque는 list에 있는 append, clear, count, extend, remove, reverse 함수를 가지고 있고, 추가로 appendleft, popleft, extendleft, 와 rotate 함수를 가지고 있습니다. 여기서는 deque에만 있는 함수들만 알아보도록 하겠습니다.

appendleft(x)

appendleft는 왼쪽 첫 번째 인자를 추가하는 메소드입니다.

1
2
3

from collections import deque
a = deque([i for i in range(10)]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.appendleft(-1) # deque([-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

1
2
3

from collections import deque
a = deque([i for i in range(10)]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.appendleft([-1, -2])            # deque([[-1, -2], 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

extendleft(iterable)

extend는 append와 다르게 인수의 배열을 한 차원 낮추어 추가합니다.

1
2
3

from collections import deque
a = deque([i for i in range(10)]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.extendleft([-1, -2])            # deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

2D array를 넣으면 1D array로 추가됩니다.

1
2
3

from collections import deque
a = deque([i for i in range(10)]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.extendleft([[-1, -2]]) # deque([[-1, -2], 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

popleft()

popleft는 왼쪽 첫 번째 인자를 제거하고 반환하는 메소드입니다.

1
2
3

from collections import deque
a = deque([i for i in range(10)]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.popleft()                       # deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

rotate(n=1)

rotate(n)는 n 만큼 큐를 회전시키며 기본적으로 n=1 입니다. 양수일 때 오른쪽으로 회전시키고 음수일 때 왼쪽으로 회전합니다.

from collections import deque
a = deque([i for i in range(10)]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.rotate(-1)                      # deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])
a.rotate(1)                       # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
a.rotate(3)                       # deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6])

Performance

list를 이용하여 큐를 구현할 수 있지만 deque를 사용하는 이유 중 하나는 성능입니다. list.pop(0)와 deque.popleft()의 실행 시간을 timeit을 이용하여 측정해보겠습니다. timeit에 대한 자세한 설명은 포스팅을 참고해주세요

setup = """
a=[i for i in range(10**7)]
"""
timeit.timeit('a.pop(0)', setup=setup, number=1) # 0.03873537702020258

setup = """
from collections import deque
a = deque([i for i in range(10**7)])
"""

timeit.timeit('a.popleft()', setup=setup, number=1) # 6.488000508397818e-06

list.pop(0)의 경우 O(N)의 시간복잡도를 가지지만 deque.popleft()는 O(1)로 매우 빠릅니다.

Python Collections Deque