[Python] deque 사용하기

 

파이썬에서 큐(queue) 자료구조를 사용하는 방법은

1. list 사용하기 
2. deque 사용하기 
3. Queue 클래스 사용하기

등이 있다. 그중 deque에 대해 자세히 알아보려고 한다. 

 

 

 

 

deque

• deque는 collections 모듈에서 사용할 수 있다. 
• deque는 “double-ended queue”의 약자이며, 스택과 큐를 일반화한 것으로, 양방향에서 원소를 추가하고 제거할 수 있는 자료구조이다.
• 양쪽 끝에서의 추가와 제거를 O(1) 성능으로 지원한다.
• deque는 내부적으로 linked list를 사용하고 있어 무작위로 접근할 경우 O(n) 시간 복잡도를 가진다. 

 

 

 

deque가 지원하는 메서드는 다음과 같다.

append(x)	데크의 오른쪽에 x를 추가합니다.
appendleft(x)	데크의 왼쪽에 x를 추가합니다.
clear()	데크에서 모든 요소를 제거하고 길이가 0인 상태로 만듭니다.
copy()	데크의 얕은 복사본을 만듭니다.
count(x)	x 와 같은 데크 요소의 수를 셉니다.
extend(iterable)	iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장합니다.
extendleft(iterable)	iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장합니다. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 줍니다.
index(x[, start[, stop]])	데크에 있는 x의 위치를 반환합니다 (인덱스 start 또는 그 이후, 그리고 인덱스 stop 이전). 첫 번째 일치를 반환하거나 찾을 수 없으면 Value Error를 발생시킵니다.
insert(i, x)	x를 데크의 i 위치에 삽입합니다. 삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면, Index Error가 발생합니다.
pop()	데크의 오른쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, Index Error를 발생시킵니다.
popleft()	데크의 왼쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, Index Error를 발생시킵니다.
remove(value)	value의 첫 번째 항목을 제거합니다. 찾을 수 없으면, Value Error를 발생시킵니다.
reverse()	데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환합니다.
rotate(n=1)	데크를 n 단계 오른쪽으로 회전합니다. n이 음수이면, 왼쪽으로 회전합니다.
maxlen	데크의 최대 크기 또는 제한이 없으면 None.

 

이 중 queue 자료구조 구현은 append(x), popleft()를 사용한다.

queue는 선입선출의 자료구조로 먼저 들어간 원소가 먼저 나오는 구조이다.

따라서 append(x)를 통해 원소를 추가해주고 원소를 제거할 때는 제일 먼저 들어간 원소를 popleft()를 통해 제거한다.

 

 

append(x)

from collections import deque

queue = deque()

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

 

 

popleft()

from collections import deque

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

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

 

 

maxlen

그리고 deque는 maxlen을 통해 길이의 최댓값을 설정할 수 있다. 그리고 만약 그 길이 이상 원소를 추가하게 되면 맨 앞 (또는 맨 뒤) 원소가 삭제된 후, 추가된다.

• append() : 맨 왼쪽 원소가 삭제된 후, 맨 오른쪽에 원소가 추가된다.
• appendleft(): 맨 오른쪽 원소가 삭제된 후, 맨 왼쪽에 원소가 추가된다.

from collections import deque

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

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

 

 

https://docs.python.org/ko/3/library/collections.html#collections.deque