[Python] Deque

 

list를 이용해서 queue처럼 사용할 수 있습니다.

queue = [1, 2, 3]
queue.append(4)    #[1, 2, 3, 4]
queue.pop(0)       #[2, 3, 4]
queue.insert(0, 5) #[5, 2, 3, 4]

하지만 list를 queue처럼 사용하는 것은 성능 측면에서 추천되지 않습니다.

list는 Random Access에 최적화된 자료구조이기 때문에 pop(0), insert(0, x)는 성능적으로 매우 불리한 연산입니다.

이 연산의 시간 복잡도는 O(n)입니다.

 

Deque

collections 모듈의 deque를 사용해서 queue, stack 자료구조를 구현할 수 있습니다.

collections에 queue도 있지만 Deque가 훨씬 빠르니 코딩테스트에서는 Deque를 사용하는 것이 좋습니다.

 

method

append(item)	item을 deque의 맨 뒤(오른쪽 끝)에 삽입한다.
appendleft(item)	item을 deque의 맾 앞(왼쪽 끝)에 삽입한다.
pop()	deque의 오른쪽 끝 element를 가져오는 동시에 deque에서 삭제한다.
popleft()	deque의 왼쪽 끝 element를 가져오는 동시에 deque에서 삭제한다.
extend(array)	주어진 배열(array)를 순환하면서 deque의 오른쪽에 추가한다.
extendleft(array)	주어진 배열(array)를 순환하면서 deque의 왼쪽에 추가한다.
remove(item)	item을 deque에서 찾아 삭제한다.
rotate(num)	deque를 num만큼 회전한다.(양수 : 오른쪽, 음수 : 왼쪽)

 

example

from collections import deque

n = 3
m = 4
queue = deque([1,2,3,4,5])
queue.rotate(1)             #deque([5, 1, 2, 3, 4])

queue.rotate(-1)            #deque([1, 2, 3, 4, 5])

queue.remove(4)             #deque([1, 2, 3, 5])

arr = [8, 7, 9]
queue.extend(arr)           #deque([1, 2, 3, 5, 8, 7, 9])

arr = [11, 12, 10]
queue.extendleft(arr)       #deque([10, 12, 11, 1, 2, 3, 5, 8, 7, 9])
                            #arr앞에서 부터 deque앞에 추가한다.

 

Queue

from collections import deque

queue = deque([1, 2])
queue.append(3)         #deque([1, 2, 3])
queue.append(4)         #deque([1, 2, 3, 4])

a = queue.popleft()     # a = 1
                        # deque([2, 3, 4])
b = queue.popleft()     # b = 2
                        # deque([3, 4])

 

Stack

from collections import deque

queue = deque([1, 2])
queue.appendleft(3)     #deque([3, 1, 2])
queue.appendleft(4)     #deque([4, 3, 1, 2])

a = queue.popleft()     # a = 4
                        # deque([3, 1, 2])

b = queue.popleft()     # b = 3
                        #deque([1, 2])