python deque 이용한 원형큐

파이썬 표준 라이브러리에는 **원형 큐(Circular Queue)**를 직접 구현한 자료구조는 없습니다. 하지만, 원형 큐의 기능을 구현하는 가장 좋은 방법은 **collections 모듈의 deque**를 사용하는 것입니다.

deque는 이중 종료 큐(Double-Ended Queue)로, 원형 큐의 핵심 기능인 양 끝에서의 $O(1)$ 시간 복잡도로 요소를 추가하거나 제거하는 연산을 제공하여 원형 큐처럼 효율적으로 동작할 수 있습니다.

---

🛠️ deque를 이용한 원형 큐 구현

deque (데크)는 리스트보다 훨씬 효율적으로 큐와 스택의 기능을 수행할 수 있습니다. 특히, maxlen 인자를 사용하여 최대 크기를 지정하면 원형 큐의 특성(크기 제한 및 오래된 요소 자동 제거)을 구현할 수 있습니다.

1. deque의 특징

특징	deque 메서드	시간 복잡도	원형 큐 역할
요소 추가	.append(item)	$O(1)$	큐의 **rear(뒤)**에 추가
요소 제거	.popleft()	$O(1)$	큐의 **front(앞)**에서 제거
최대 크기 제한	deque(maxlen=N)	-	큐가 가득 차면 가장 오래된 요소(FIFO)를 자동으로 제거

2. 최대 크기 제한 (원형 큐 기능 구현)

maxlen을 지정하면, 큐가 가득 찼을 때 새로운 요소가 들어오면 가장 먼저 들어온(오래된) 요소를 자동으로 제거하는 원형 큐와 같은 동작을 수행합니다.

from collections import deque

# 최대 크기가 3인 원형 큐 생성
circular_queue = deque(maxlen=3) 

# 1단계: 요소 추가 (정상)
circular_queue.append(10)
circular_queue.append(20)
print(f"1단계: {circular_queue}") # 출력: deque([10, 20], maxlen=3)

# 2단계: 최대 크기 초과 요소 추가
circular_queue.append(30)
circular_queue.append(40)  # 큐가 가득 찼으므로, 가장 오래된 요소 '10'이 자동 제거됨

print(f"2단계: {circular_queue}") # 출력: deque([20, 30, 40], maxlen=3)

# 3단계: 요소 제거 (popleft 사용)
removed_item = circular_queue.popleft() 
print(f"3단계: 제거된 항목: {removed_item}") # 출력: 제거된 항목: 20
print(f"3단계: 현재 큐: {circular_queue}") # 출력: deque([30, 40], maxlen=3)

따라서 파이썬에서 원형 큐의 개념과 기능을 구현하고자 한다면, 별도로 클래스를 구현하기보다는 **collections.deque**를 사용하는 것이 가장 효율적이고 권장되는 방법입니다.