[자료구조] 파이썬의 deque - 양방향 큐, 원형 큐 구현

list가 [1,2,3,4,5]로 주어질 때,

배열의 끝에서 원소 추출하는 list.pop() 후에는 [1 ,2 ,3, 4]로 재정렬이 필요 없지만 (O(1)),

배열의 시작에서 추출하는 list.pop(0) 후에는 [2, 3, 4, 5]로 원소를 한 칸씩 옮겨주는 작업이 필요해,

시간 복잡도는 O(n)이 된다.

 

list의 앞과 뒤 모두에서 원소의 추가와 삭제가 일어난다면, 이런 이유로

양방향 큐, 혹은 원형 큐를 사용하는 것이 더 이익이다.

 

파이썬에는 이를 이미 구현한 라이브러리가 있다.

 

 

collections 모듈 - deque (Doubley-Ended Queue)

deque는 덱이라고 읽으면 된단다.

from collections import deque

# declare queue
queue = deque(['a','b','c'])

print(queue)
# result - deque(['a','b','c'])

 

# 큐의 끝에 삽입
queue.append('d') # ['a','b','c','d']

# 큐의 앞에 삽입
queue.appendleft('e') # ['e','a','b','c','d']

# 큐의 끝에서 삭제
queue.pop() # ['e','a','b','c']

# 큐의 앞에서 삭제
queue.popleft() # ['a','b','c']

 

여기서 중요한 함수는 .rotate()이다.

매개변수가 음수 (-) 이면 왼쪽으로, 양수 (-) 이면 오른쪽으로 덱을 '이동'시킨다!

queue = deque(['a','b','c'])

queue.rotate(-1)
print(queue) # ['b','c','a']

queue2 = deque(['a','b','c'])

queue2.rotate(1)
print(queue2) # ['c','a','b']

 

이 외에도

- clear() : 덱 전체를 비워 length = 0으로 만든다

- copy() : 덱 전체를 카피

- count(x) : x가 덱에서 몇 번이나 나타나는 지 셈

- extend(iterable) : iterable안 원소들 모두를 덱의 끝에 덧붙임

- index(x [start [, stop]]) : start와 stop 사이에서 x의 위치를 반환

- insert(x, i) : x를 i인덱스에 삽입

- remove(x) : 처음 나타나는 x를 덱에서 삭제

- reverse() : 원소의 순서를 in-place 역순으로 바꿈

- maxlen : 덱의 최대 사이즈.

 

 

함수들을 쓸 수 있다.

참고 - docs.python.org/3/library/collections.html#collections.deque