deque (Double-Ended Queue)

deque란?

• 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐
• 파이썬에서는 collections.deque 사용
• 일반 list보다 큐 구현에 훨씬 효율적 (양쪽 모두 O(1))

from collections import deque

---

주요 메서드

메서드	설명
append(x)	오른쪽에 추가
appendleft(x)	왼쪽에 추가
pop()	오른쪽에서 제거
popleft()	왼쪽에서 제거
extend(iter)	오른쪽에 여러 개 추가
extendleft(iter)	왼쪽에 여러 개 추가
rotate(n)	n만큼 회전 (오른쪽: 양수 / 왼쪽: 음수)
reverse()	순서 뒤집기

---

사용 예제

큐처럼 사용 (왼쪽에서 꺼냄)

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.popleft()  # 1
q.popleft()  # 2

스택처럼 사용 (오른쪽에서 꺼냄)

s = deque()
s.append(10)
s.append(20)
s.pop()  # 20

양쪽 삽입/삭제

dq = deque()
dq.append(1)        # [1]
dq.appendleft(0)    # [0, 1]
dq.append(2)        # [0, 1, 2]
dq.pop()            # 2
dq.popleft()        # 0

---

시간 복잡도

연산	시간복잡도
append, appendleft	O(1)
pop, popleft	O(1)

리스트로 구현 시 pop(0)은 O(N)

→ 큐는 무조건 deque로 구현

---

활용 예시

• 일반 큐 (BFS)
• 스택 + 큐 복합 문제
• 양쪽 삽입/삭제 필요한 시뮬레이션 문제
• 슬라이딩 윈도우 최적화 문제
• LRU 캐시

---

입력 최적화 예제

import sys
from collections import deque

input = sys.stdin.readline
dq = deque()

n = int(input())
for _ in range(n):
    cmd = input().strip()
    if cmd.startswith("push"):
        _, x = cmd.split()
        dq.append(int(x))
    elif cmd == "pop":
        print(dq.popleft() if dq else -1)
    elif cmd == "size":
        print(len(dq))
    elif cmd == "empty":
        print(1 if not dq else 0)
    elif cmd == "front":
        print(dq[0] if dq else -1)
    elif cmd == "back":
        print(dq[-1] if dq else -1)

---

클래스 큐 구현 시 핵심 포인트

self.front = (self.front + 1) % self.size
self.count -= 1

• 실제 데이터를 삭제하진 않음
• front 포인터 이동 + 원소 수 감소로 제거 처리
• 원형 큐 방식에서 성능과 공간 효율 확보

---

핵심 요약

• deque는 리스트보다 빠른 큐/스택 구현 가능
• 큐/스택/슬라이딩 윈도우 모두 대응 가능
• 앞뒤 삽입/삭제 모두 필요한 경우 반드시 사용