[Python] deque(데크)

GeeksforGeeks에 따르면 Deque에 대한 설명은 아래와 같다.

:Deque (Doubly Ended Queue) in Python is implemented using the module “collections“. Deque is preferred over a list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to a list that provides O(n) time complexity.

: "colletions" 모듈을 implement해 사용한다. Deque는 데이터를 담는 자료구조(Container)로 빠른 append와 양쪽(앞뒤)에서 pop이 필요한 경우 List보다 선호되며, 해당 연산에서 List가 O(n)의 시간 복잡도를 반해 O(1)의 시간 복잡도를 갖는다.

 

 일반적인 Queue의 경우 First In Last Out(FIFO)의 방식인 반면 Deque는 이름(Doubly Ended Queue)에서도 알 수 있듯이 앞쪽에서도 pop이 가능하고 뒤쪽에서도 push와 pop이 가능하다. 이것이 Deque가 앞서 설명한 상황에서 O(1)의 시간 복잡도를 갖게 하는 이유고, Python에서 Queue를 사용할 경우 Deque를 선호하는 이유다.

 예를 들어, List의 경우 마지막 index에 위치한 요소를 지울 땐 O(1)의 시간 복잡도를 갖지만, 첫 번째 index에 위치한 요소를 지울 땐 해당 요소를 지우고 모든 요소를 한 index씩 앞으로 옮겨야 하기에 O(n)의 시간 복잡도를 갖게 된다. 반면 Deque의 경우 pop()과 popleft()를 통해 각각 마지막 또는 첫 번째 요소를 지우기만 하면 돼 O(1)의 시간 복잡도를 가질 수 있고, 요소를 추가하는 경우에도 append()와 appendleft()를 통해 같은 효과를 볼 수 있다.

 List와의 비교를 좀 더 해보자면 List의 경우 index를 통한 접근이 가능하지만 Deque는 불가능 하기에 상황에 따라 사용해야한다.

 

아래는 간단한 사용 예시다.

from collections import deque

q = deque([])

q.append(1)
q.append(2)
q.appendleft(3)
print(q)

print(q.popleft())
print(q.pop())

실행 결과:

deque([3, 1, 2])

3

2

 

출처

- https://www.geeksforgeeks.org/deque-in-python/

- https://codingpractices.tistory.com/entry/Python%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%99%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%8C%80%EC%8B%A0-%ED%81%90-%EB%8D%B0%ED%81%AC-deque-%EB%A5%BC-%EC%93%B8%EA%B9%8C

- https://daimhada.tistory.com/107