[Python] deque를 list 대신 써야하는 이유가 뭘까?

 

deque 이란?

---

결론부터 말씀드리자면 list 와 같은 배열이지만 "양쪽에서 요소를 추가와 삭제가 가능한" 자료구조입니다.

 

Python의 collections 모듈에서 제공하는 deque는 "double-ended queue"(양방향 큐)의 줄임말 입니다. 다시 말해서 queue(큐)에 앞쪽에 연산이 추가된 자료구조라고 볼 수 있습니다.

 

써야하는 이유

---

deque 자료구조는 pop, append method는 시간복잡도가 O(1)입니다.

하지만 list 자료구조에서 pop, append method는 시간복잡도가 O(n)입니다.

이러한 이유로 작은 데이터 셋에서는 큰 차이가 없지만 데이터 셋이 큰 경우에 큰 차이를 알 수 있습니다.

특히 BFS를 queue로 구현하면 시간초과가 발생하지만 deque를 통해 구현하면 시간초과가 발생하지 않습니다.

 

그러므로 간단하거나 작은 데이터의 경우에는 list, 그 외의 경우에는 deque를 사용하는 것을 추천합니다.

 

메소드 종류

---

import collections

d = collections.deque()

 

메소드	설명
d.append(item)	덱의 오른쪽에 요소(item)을 추가합니다.
d.appendleft(item)	덱의 왼쪽에 요소(item)을 추가합니다.
d.pop()	덱의 오른쪽에 요소(item)을 제거하면서 반환합니다.
d.popleft()	덱의 왼쪽에 요소(item)을 제거하면서 반환합니다.
d.extend(array)	덱의 오른쪽에 array를 추가합니다.
d.extendleft(array)	덱의 왼쪽에 array를 "뒤집어서" 추가합니다.
d.rotate(n)	덱을 양수면 n 만큼 오른쪽으로, 음수면 n 만큼 왼쪽으로 회전합니다.

 

구현 방법

---

 

from collections import deque
d = deque('ghi')                 # 'g', 'h' 'i' 요소를 가진 deque 생성합니다.
for elem in d:                   # deque 요소를 순회하며 출력합니다.
    print(elem.upper())
    
# 출력결과
# G
# H
# I 

d.append('j')                    		# 오른쪽에 'j'를 추가합니다.
d.appendleft('f')                		# 왼쪽에 'f'를 추가합니다.
print(d)                         		# deque 출력합니다.
# deque(['f', 'g', 'h', 'i', 'j'])

print(d.pop())                          # 오른쪽 요소를 제거 및 반환되면서 출력합니다.
# j
print(d.popleft())                      # 왼쪽 요소를 제거 및 반환되면서 출력합니다.
# f
print(list(d))                          # deque의 요소를 모두 출력합니다.
# ['g', 'h', 'i']
print(d[0])                             # 왼쪽의 첫번재 요소 출력합니다.
# g
print(d[-1])                            # 오른쪽의 첫번째 요소 출력합니다.
# i

print(list(reversed(d)))                # deque의 요소를 반전합니다.
# ['i', 'h', 'g']
print('h' in d)                         # deque안에 요소 찾기합니다.
# True
d.extend('jkl')                  		# 오른쪽에 array를 추가합니다.
print(d)
# deque(['g', 'h', 'i', 'j', 'k', 'l'])
d.rotate(1)                      		# 오른쪽으로 1만큼 회전합니다.
print(d)
# deque(['l', 'g', 'h', 'i', 'j', 'k'])
d.rotate(-1)		                     # 왼쪽으로 1만큼 회전합니다.
print(d)
# deque(['g', 'h', 'i', 'j', 'k', 'l'])

print(deque(reversed(d)))               # deque를 반전시킵니다.
# deque(['l', 'k', 'j', 'i', 'h', 'g'])
d.clear()                        		# deque의 요소들을 모두 제거합니다.
d.pop()                          		# deque의 요소들이 없어서 오류를 발생시킵니다.
# 오류출력
# Traceback (most recent call last):
#    File "<pyshell#6>", line 1, in -toplevel-
#        d.pop()
# IndexError: pop from an empty deque

d.extendleft('abc')              # c -> b -> a 순으로 왼쪽에 추가하기 때문에 뒤집에서 추가됩니다.
print(d)
# deque(['c', 'b', 'a'])

 

관련문제들

---

https://www.acmicpc.net/problem/10845

10845번: 큐

list와 deque를 모두 구현해볼 수 있는 문제입니다.

 

https://www.acmicpc.net/problem/7569

7569번: 토마토

list로 구현하면 시간초과가 발생하고 deque로 구현하면 시간초과가 발생하지 않는 문제입니다.

 

 

참고문헌 : https://docs.python.org/ko/3/library/collections.html#collections.deque