💻[Python] 파이썬에서 자료구조 덱(deque) 사용하기

파이썬 공식문서에서 자료구조 덱(deque) 사용법과 관련 함수들을 확인할 수 있다.

 

class collections.deque([iterable])

---

1. 덱(deque)이란?

Double Ended Queue이다. stack과 queue를 합쳐 놓은 자료구조이다. 자료의 양 끝에서 삽입/삭제 연산이 이루어진다.

 

Stack, Queue (출처: https://www.happycoders.eu/algorithms/stack-queue-deque-java/)

Deque

 

덱의 모든 연산의 시간 복잡도는 O(1)이다. 

 

2. 파이썬에서 덱 사용하기

파이썬에서 list를 사용하는 것과 비슷한데, deque이 시간 복잡도 측면에서 훨씬 유리하다. list의 크기가 작을 때는 상관 없겠지만, 리스트의 크기가 아주 커진다면 리스트의 삽입과 삭제 연산은 아주 복잡해진다.

 

list의 삭제 연산의 시간 복잡도는 O(n)이고, deque의 삭제 연산의 시간 복잡도는 O(1)이다.

 

파이썬에서는 collections 모듈에 deque 클래스로 deque 자료 구조가 이미 구현되어 있다. 

 

덱의 선언 방법과 주요 함수들의 사용 방법은 다음과 같다.

 

from collections import deque

dq = deque() # 덱 선언하기

dq.append(10)

dq.insert(5, 10) # 인덱스가 5인 자리에 10이라는 요소 삽입

dq.extend([0, 0, 0]) # 덱의 오른쪽에 iterable한 객체를 통째로 append하여 연장
dq.extend([1, 1, 1]) # 덱의 왼쪽에 iterable한 객채를 통째로 append하여 연장

d.pop() # 덱의 오른쪽에서 요소 하나 삭제
d.popleft() # 덱의 왼쪽에서 요소 하나 삭제

list_dq = list(dq) # 일반 list로도 변환 가능

 

from collections import deque

dq = deque([1, 2, 3, 4]) # 선언과 동시에 초기화 가능

dq.clear() # 모든 요소 삭제