deque 모듈

deque 모듈

deque(데크, double-ended queue) 모듈은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.
즉, 스택과 큐를 모드 지원하는 모듈로 Python의 collections 모듈에서 제공됩니다.
deque를 사용하기 위해서는 리스트와 비슷한 형식으로 데이터를 저장해야 합니다.

기본적인 사용법

Import 방법

from collections import deque

생성

d = deque([1, 2, 3, 4])

삽입 / 삭제

for i in range(5):  
    deque_list.append(i) # 오른쪽 끝에 삽입  
print(deque_list)  
# deque([0, 1, 2, 3, 4])

deque_list.pop() # 오른쪽 끝 요소 삭제
print(deque_list)  
# deque([0, 1, 2, 3])

for i in range(5):  
    deque_list.appendleft(i) # 왼쪽 끝에 삽입
print(deque_list)  
# deque([4, 3, 2, 1, 0]) 

deque_list.popleft() # 왼쪽 끝 요소 삭제
print(deque_list)  
# deque([3, 2, 1, 0])

조회

d[0]  # 첫 번째 요소 조회
d[-1]  # 마지막 요소 조회

길이

len(d)  # deque의 길이

장점 및 특징

deque 모듈은 리스트에 비해 일반적인 스택과 큐 연산에 더 효율적입니다.
또한 양쪽에서의 삽입, 삭제가 O(1) 시간 복잡도로도 가능합니다. 이로 얻는 장점은 아래 예제에서 확인하겠지만, 리스트에 비해 삽입, 삭제 연산이 매우 빠릅니다.

이러한 장점을 갖는 이유는 deque가 연결 리스트(Linked list)의 특성을 지원하기 때문입니다.

참고로 연결 리스트는 데이터를 저장할 때 요소의 값을 한 쪽으로 연결한 후, 요소의 다음 값의 주소값을 저장하여 데이터를 연결하는 기법입니다.

연결 리스트는 다음 요소의 주소값을 저장하므로 데이터를 원형으로 저장할 수 있고, 마지막 요소에 첫 번째 값의 주소를 저장한다면 해당 값을 찾아갈 수 있습니다. 이러한 특징 때문에 가능한 기능 중 하나가 rotate() 함수입니다. rotate(n)은 요소들을 n값 만큼 회전하는 함수입니다. n이 양수이면 오른쪽으로 회전하고, n이 음수이면 왼쪽으로 회전합니다.

from collections import deque  

deque_list = deque([2, 4, 6, 8])  
print(deque_list)  
# deque([2, 4, 6, 8])  

deque_list.rotate(1)  
print(deque_list)  
# deque([8, 2, 4, 6])  

deque_list.rotate(-1)  
print(deque_list)  
# deque([2, 4, 6, 8])

rotate() 함수는 이처럼 각 요소와 인덱스 번호를 하나씩 옮깁니다.

deque모듈의 추가적인 함수들

reversed()

reversed()함수는 기존과 반대로 데이터를 저장할 수 있습니다.

deque_list = deque([1, 2, 3, 4])  
reversed_deque = deque(reversed(deque_list))  
print(reversed_deque)  
# deque([4, 3, 2, 1])

clear()

deque리스트를 모두 지웁니다.

deque_list = deque()  
for i in range(4):  
    deque_list.append(i)  
print(deque_list)  
# deque([0, 1, 2, 3])  

deque_list.clear()  
print(deque_list)  
# deque([])

extend(), extendleft()

extend()와 extedleft()는 리스트가 통째로 추가됩니다.

deque_list = deque([1, 2, 3])  

deque_list.extend([4, 5, 6])  
print(deque_list)  
# deque([1, 2, 3, 4, 5, 6])  

deque_list.extendleft([0, -1, -2])  
print(deque_list)  
deque([-2, -1, 0, 1, 2, 3, 4, 5, 6])

maxlen

maxlen은 deque의 매개변수로 deque의 사이즈를 고정하는 인자값입니다.

data = [1, 2, 3, 4, 5, 6, 7]  
deque_list = deque(data, maxlen=3)  
print(deque_list)  
# deque([5, 6, 7], maxlen=3)

deque와 list의 성능 테스트 비교

from collections import deque  
import time  


# insert 성능 비교  

# deque  
deque_list = deque()  
start = time.time() # second단위  

for i in range(100000):  
    deque_list.insert(1, "x")  

end = time.time()  
print("deque insert 시간: ", end - start)  
# deque insert 시간:  0.012130975723266602  

# list  
list = list()  
start = time.time()  

for i in range(100000):  
    list.insert(1, "x")  

end = time.time()  
print("list insert 시간: ", end - start)  
# list insert 시간:  4.031864166259766  


# 추출 성능 비교  

# deque start = time.time()  
for i in range(100000):  
    deque_list.pop()  
end = time.time()  
print("deque pop 시간: ", end - start)  
# deque pop 시간:  0.0071468353271484375  

# list  
start = time.time()  
for i in range(100000):  
    list.pop()  
end = time.time()  
print("list pop 시간: ", end - start)  
# list pop 시간:  0.007027149200439453  

# 아래 부분을 테스트 하기 위해서는 pop 부분 코드를 주석 처리해야 합니다.

# deque  
start = time.time()  
for i in range(100000):  
    deque_list.popleft()  
end = time.time()  
print("deque pop 시간: ", end - start)  
# deque pop 시간:  0.00786733627319336  

# list  
start = time.time()  
for i in range(100000):  
    list.pop(0)  
end = time.time()  
print("list pop 시간: ", end - start)  
# list pop 시간:  1.268723964691162

이를 통해 deque가 list에 비해 빠르다는 것을 알 수 있습니다.