파이썬 deque 모듈
- double-ended queue (양쪽 끝에서 데이터를 삽입/삭제할 수 있는 큐)
- collections 모듈에 포함되어 있고,
내부적으로 이중 연결 리스트(doubly linked list) 로 구현되어 있어 양쪽 끝에서 O(1) 시간에 삽입/삭제가 가능
- 파이썬 리스트(list)는 맨 앞쪽에서 요소를 삽입/삭제할 때 O(n)시간이 걸리지만, deque는 O(1) 성능을 보장
deque 모듈에 주요 메서드
삽입/삭제
append(x) : 오른쪽(뒤)에 요소 추가
appendleft(x) : 왼쪽(앞)에 요소 추가
pop() : 오른쪽(뒤) 요소 제거 후 반환
popleft() : 왼쪽(앞) 요소 제거 후 반환
확장
extend(iterable) : iterable을 오른쪽에 확장
extendleft(iterable) : iterable을 왼쪽에 확장 (역순으로 들어감)
회전
rotate(n) : 양수 n이면 오른쪽으로 회전, 음수 n이면 왼쪽으로 회전
제거/삽입
insert(i, x) : 인덱스 i에 요소 삽입
remove(x) : 첫 번째로 등장하는 x 삭제
기타
clear() : 모든 요소 제거
count(x) : x의 개수 세기
reverse() : deque를 제자리에서 뒤집기
maxlen : deque 생성 시 최대 길이 지정 가능 (슬라이딩 윈도우 등에 활용)
deque 활용 (큐, 스택, 연결리스트, 슬라이딩 윈도우)
(1) FIFO 큐
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft()) # 1
print(queue.popleft()) # 2
print(queue.popleft()) # 3
(2) 스택 (LIFO 구조)
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop()) # 3
print(stack.pop()) # 2
print(stack.pop()) # 1
(3) 연결리스트
linked = deque([10, 20, 30])
linked.appendleft(5) # 앞에 추가
linked.append(40) # 뒤에 추가
linked.insert(2, 15) # 인덱스 2에 삽입
print(linked) # deque([5, 10, 15, 20, 30, 40])
linked.remove(20)
print(linked) # deque([5, 10, 15, 30, 40])
(4) 슬라이딩 윈도우
maxlen 속성을 활용하면 고정 크기 버퍼나 슬라이딩 윈도우를 쉽게 구현 가능
from collections import deque
window = deque(maxlen=3) # 최대 길이 3
for i in range(1, 7):
window.append(i)
print(list(window))
'''
[1]
[1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]
'''