[Python] 자료구조 - collections 모듈 - deque

[Collections 모듈]

Collection 모듈은 파이썬에서 제공하는 내장 자료구조 모듈입니다. Collections 모듈은 앞선 포스팅에서 소개한 리스트, 튜플, 딕셔너리 등을 확장하여 제공합니다. 제공하는 모듈로는 deque, OrderedDict, defaultdict, Counter, namedtuple 등이 있습니다.

import collections

from collections import deque
from collections import OrderedDict
from collections import defaultdict
from collections import Counter
from collections import namedtuple

 

[deque 모듈]

'데크'라고 읽는 deque 모듈은 double-ended queue를 줄인 말입니다. 앞서 소개한 스택과 큐를 모두 지원하는 모듈입니다. 스택은 1-2-3-4-5로 입력한 데이터를 5-4-3-2-1의 순서로 출력하고, 큐는 1-2-3-4-5로 입력한 데이터를 1-2-3-4-5로 출력하는 자료구조입니다. 데크는 스택과 큐의 두 가지 서로 다른 출력 방식을 모두 구현할 수 있습니다.

• deque에 입력

deque는 리스트와 비슷한 형식으로 데이터를 저장하여 사용합니다. append() 함수를 사용하면 기존의 리스트와 같이 데이터에 index 번호를 하나씩 늘려가며 맨 뒤에 데이터를 추가할 수 있습니다.

from collections import deque

dq = deque()
for i in range(5):
	dq.append(i)
print(dq)
'''
>>> dq([0, 1, 2, 3, 4])
'''

• deque - 스택 처럼 출력

pop() 함수를 사용하면, 스택처럼 오른쪽 요소부터 하나씩 추출할 수 있습니다. 

print(dq.pop())
print(dq.pop())
print(dq)
'''
>>> 4
>>> 3
>>> dq([0, 1, 2])
'''

• deque - 큐 처럼 출력

deque를 큐 처럼 출력하려면 pop(0)를 사용하면 될까요? 안타깝게도 pop(0)은 deque에서 실행되지 않습니다. 대신 값을 추가할 때 append() 대신 appendleft()를 사용하면 deque의 오른쪽이 아닌 왼쪽에 새로운 값을 입력할 수 있게 됩니다. 그 다음 pop()을 사용하게 되면, 기존의 큐와 같이 가장 먼저 들어간 데이터가 가장 먼저 출력되도록 할 수 있습니다.

from collections import deque

dq = deque()
for i in range(5):
	dq.appendleft(i)
print(dq)
'''
>>> dq([4, 3, 2, 1, 0])
'''

• deque와 list의 차이

위의 설명만 보았을 때, deque와 list가 어떤 차이가 있는지 쉽게 이해되지 않을 수 있습니다. 그러나 deque는 '연결 리스트(linked list)'의 특성을 지원합니다. 연결 리스트는 데이터를 저장할 때 요소의 값만 저장하는 것이 아니라, 요소의 다음 값의 주소값을 함께 저장하여 데이터를 연결합니다. 그리고 마지막 데이터는 첫 번째 데이터의 주소값을 함께 저장합니다. 그렇게 되면 모든 데이터가 서로의 꼬리를 물고 연결된 연결 리스트가 됩니다. 이러한 특징으로 인해, 실제 저장된 주소값을 변경하지 않더라도 인덱스 번호만 하나씩 옮겨서 간단히 인덱스를 수정할 수 있게 됩니다.

• deque에서 사용 가능한 함수들

- rotate(n): 기존 deque에 저장된 요소들의 값 인덱스 n칸씩 이동

- reversed(): 기존과 반대로 인덱스를 반전한 deque 반환

- extend(), extendleft(): 리스트를 통째로 오른쪽이나 왼쪽으로 추가

• deque 장점

deque 모듈은 메모리의 효율적 사용과 빠른 처리 속도를 장점으로 가집니다. 따라서 대용량의 큐나 스택을 처리할 일이 있다면 deque를 사용하는 것이 좋습니다.