[자료형 라이브러리] collections.deque (데크)

collections 모듈에는 파이썬의 범용 내장 자료형인 dict, list, set, tuple에 대한 대안으로 특수 컨테이너 데이터형이 구현되어있다. 

그중 deque는 양방향으로 빠르게 추가 및 삭제를 할 수 있는 리스트류의 객체이다.

 

개념

일반 큐(queue)는 선입선출으로 FIFO방식으로 작동하지만, deque는 양방향 큐로써 앞과 뒤에서 데이터를 추가, 삭제할 수 있다.

따라서 deque는 스택처럼 써도 되고, 큐처럼 쓸 수도 있다.

collections.deque 모듈은 이러한 deque 자료형을 생성하는 모듈이다.

class collections.deque([iterable[,maxlen]])

from collections import deque

#iterable로 부터 왼쪽에서 오른쪽 순인 데이터로 초기화 된 새로운 데크 객체를 반환하고 (g h i 출력됨)
d = deque('ghi')
for i in d:
	print(i)

#iterable이 비어있다면 비어있는 새로운 데크 객체를 반환한다.
d = deque()

deque는 데크라고 읽고, double-ended queue의 줄임말이다.

데크는 양방향에서 thread-safe하고 메모리 효율이 좋은 append와 pop을 지원하며, 시간복잡도는 거의 O(1)에 가깝다.

리스트도 비슷한 연산을 제공하지만, 사이즈와 위치를 바꾸는 insert와 pop에 시간복잡도가 O(n)이다.

 

데크 사용법

from collections import deque

#deque 모듈 임포트 후 빈 데크 객체 생성
deq = deque([3,4,5,6])
n = 3
m = -2

#앞부분에 삽입
deq.appendleft(1)
#deque([1,3,4,5,6])

#뒷부분에 삽입
deq.append(9)
#deque([1,3,4,5,6,9])

#앞부분 pop
deq.popleft()
#deque([3,4,5,6,9])

#뒷부분 pop
deq.pop()
#deque([3,4,5,6])

#n번 오른쪽으로 회전
deq.rotate(n)
#deque([4,5,6,3])

#m번 왼쪽으로 회전
deq.rotate(m)
#deque([6,3,4,5])

 

참고 사이트:

https://docs.python.org/3/library/collections.html#collections.deque

collections — Container datatypes — Python 3.9.6 documentation