[파이썬 100강] 65강. deque로 양쪽 끝 삽입·삭제를 O(1)로 처리하기

Last updated on 
[파이썬 100강] 65강. deque로 양쪽 끝 삽입·삭제를 O(1)로 처리하기

리스트로 큐를 구현하다가 pop(0) 때문에 느려지는 순간이 꼭 옵니다. 이번 강의는 그 지점을 해결하는 표준 도구인 collections.deque를 다룹니다. 핵심은 “양쪽 끝 작업이 많은 구조라면 list보다 deque가 맞다”는 판단 기준을 몸에 익히는 것입니다.

핵심 개념

  • deque(double-ended queue)는 양쪽 끝에서의 삽입/삭제가 빠르도록 설계된 자료구조입니다.
  • 왼쪽에서 꺼내는 작업(popleft)이 많은 큐/버퍼/슬라이딩 윈도우에서 특히 강력합니다.
  • 인덱스 기반 임의 접근이 핵심인 경우에는 여전히 list가 더 자연스러운 선택입니다.

list는 끝(append, pop)에서는 빠르지만, 맨 앞에서 빼거나 넣으면 내부 원소를 당겨야 해서 비용이 커집니다. 반면 deque는 양쪽 끝 연산을 빠르게 처리하도록 구현되어 있어 appendleft, popleft를 부담 없이 반복할 수 있습니다. 그래서 작업 대기열, BFS(너비 우선 탐색), 최근 N개 로그 유지, 실시간 이벤트 버퍼 같은 문제에서 코드가 단순해지고 성능도 안정됩니다. 중요한 점은 “무조건 deque”가 아니라, 접근 패턴이 무엇인지를 먼저 보는 것입니다. 오른쪽 끝만 쓴다면 list도 충분히 좋고, 중간 인덱스를 자주 읽고 쓰면 deque는 오히려 불편할 수 있습니다. 결국 자료구조 선택은 문법 문제가 아니라 비용 모델을 이해하는 문제입니다.

실무 연결 포인트

  • 메시지 소비자(consumer)에서 들어온 순서대로 처리할 때 큐 구현에 자주 사용합니다.
  • list의 pop(0)를 반복하면 트래픽 증가 시 지연이 급격히 커질 수 있습니다.
  • deque로 바꾸면 코드 수정이 작고 효과는 커서, 운영 중 병목 완화에 즉시 도움이 됩니다.

“느려서 서버를 키우는” 결정보다, 먼저 자료구조를 맞게 고르는 편이 훨씬 싸고 안전합니다.

기본 사용

예제 1) 큐의 기본 동작: append + popleft

>>> from collections import deque
>>> q = deque()
>>> q.append("task-1")
>>> q.append("task-2")
>>> q.append("task-3")
>>> q
deque(['task-1', 'task-2', 'task-3'])
>>> q.popleft()
'task-1'
>>> q
deque(['task-2', 'task-3'])

해설:

  • 큐(FIFO: 먼저 들어온 것이 먼저 나감) 패턴을 그대로 표현합니다.
  • list.pop(0) 대신 popleft()를 쓰면 앞쪽 제거 비용을 안정적으로 낮출 수 있습니다.

예제 2) 양쪽에서 넣고 빼기: appendleft, pop

>>> from collections import deque
>>> d = deque([2, 3])
>>> d.appendleft(1)
>>> d.append(4)
>>> d
deque([1, 2, 3, 4])
>>> d.pop()
4
>>> d.popleft()
1
>>> d
deque([2, 3])

해설:

  • 좌/우 양끝을 대칭적으로 다룰 수 있는 점이 deque의 핵심 장점입니다.
  • 양끝 작업이 많은 알고리즘(브라우저 뒤로가기/앞으로가기, 작업 스케줄러)에서 설계가 깔끔해집니다.

예제 3) 최근 N개만 유지하는 고정 버퍼

>>> from collections import deque
>>> logs = deque(maxlen=3)
>>> for event in ["login", "view", "click", "purchase", "logout"]:
...     logs.append(event)
>>> logs
deque(['click', 'purchase', 'logout'], maxlen=3)

해설:

  • maxlen을 주면 길이를 넘길 때 자동으로 오래된 항목이 밀려나갑니다.
  • “최근 100개 요청만 보관”, “최근 1분 샘플 유지” 같은 운영 요구를 매우 단순하게 구현할 수 있습니다.

예제 4) rotate로 순환 스케줄 만들기

>>> from collections import deque
>>> workers = deque(["A", "B", "C"])
>>> workers[0]
'A'
>>> workers.rotate(-1)   # 왼쪽으로 한 칸
>>> workers[0]
'B'
>>> workers.rotate(-1)
>>> workers[0]
'C'

해설:

  • rotate는 라운드로빈(순환 할당) 구현에 유용합니다.
  • 직접 인덱스 관리 코드를 쓰는 것보다 실수가 줄고 의도가 선명해집니다.

자주 하는 실수

실수 1) list를 큐로 쓰면서 pop(0) 반복하기

>>> q = ["a", "b", "c"]
>>> q.pop(0)
'a'
>>> q.pop(0)
'b'

원인:

  • list로도 동작은 하니 문제가 없어 보이지만, 데이터가 커지면 앞 제거가 누적 병목이 됩니다.

해결:

>>> from collections import deque
>>> q = deque(["a", "b", "c"])
>>> q.popleft()
'a'
>>> q.popleft()
'b'
  • 큐 의미를 가진 로직은 처음부터 deque로 선언해 성능 리스크를 예방합니다.

실수 2) deque를 list처럼 중간 인덱스 수정 중심으로 사용하기

  • 증상: 코드가 지저분해지고 성능 이점도 체감되지 않음
  • 원인: deque의 강점은 양끝 연산인데, 중간 위치 삽입/수정 중심으로 사용함
  • 해결: 중간 편집·랜덤 접근이 핵심이면 list를 사용하고, 큐/버퍼 성격이면 deque로 분리

실수 3) maxlen 동작을 모른 채 데이터 유실을 버그로 오해하기

>>> from collections import deque
>>> d = deque([1, 2, 3], maxlen=3)
>>> d.append(4)
>>> d
deque([2, 3, 4], maxlen=3)

원인:

  • maxlen이 넘치면 자동으로 반대쪽 오래된 항목이 제거된다는 규칙을 놓침

해결:

  • 최근값 유지가 목적일 때만 maxlen을 사용하고, 전체 이력 보존이 필요하면 별도 저장소(DB/파일/로그)로 분리합니다.
  • 팀 문서에 “고정 버퍼 정책(보존 개수, 유실 허용 여부)”를 명시합니다.

실무 패턴

  • 입력 검증 규칙

    • 큐에 넣기 전 이벤트 스키마(필수 키, 타입, timestamp)를 검사합니다.
    • 비정상 이벤트는 큐에 태우기 전에 드롭하거나 DLQ(Dead Letter Queue)로 분리합니다.

  • 로그/예외 처리 규칙

    • popleft 시 빈 큐 접근 가능성이 있으면 사전 길이 체크 또는 예외 처리(IndexError)를 둡니다.
    • 소비 루프에서 실패한 작업은 재시도 횟수와 지수 백오프를 함께 기록합니다.

  • 재사용 함수/구조화 팁

    • enqueue_task, dequeue_task, peek_task 같은 래퍼 함수를 두면 자료구조 교체가 쉬워집니다.
    • 비즈니스 로직이 deque API에 직접 강하게 결합되지 않도록 계층을 나눕니다.

  • 성능/메모리 체크 포인트

    • 무한 큐는 메모리 누수처럼 보일 수 있으므로 상한(maxlen 또는 워터마크) 정책을 둡니다.
    • 처리량(초당 입력/소비량)을 수치화해 큐 적체가 늘어나는 구간을 알람으로 잡습니다.

아래는 작은 소비자 루프 패턴입니다.

>>> from collections import deque
>>> tasks = deque([{"id": 1}, {"id": 2}, {"id": 3}])
>>> done = []
>>> while tasks:
...     t = tasks.popleft()
...     done.append(t["id"])
>>> done
[1, 2, 3]

이 패턴은 단순하지만, 운영 코드에서는 여기에 타임아웃·재시도·실패 큐 분리가 붙습니다. 핵심은 “큐는 쌓는 곳이 아니라 흐르게 만드는 구조”라는 점입니다.

오늘의 결론

한 줄 요약: 앞/뒤 삽입·삭제가 빈번한 문제는 list가 아니라 deque로 시작해야 성능과 가독성을 동시에 잡을 수 있습니다.

기억할 것:

  • 큐(FIFO) 구현은 append + popleft가 정석입니다.
  • 최근 N개 보존은 maxlen으로 간결하게 해결됩니다.
  • 랜덤 접근·중간 편집 중심 작업은 list가 더 적합합니다.

연습문제

  1. 문자열 작업 목록 ['build', 'test', 'deploy']를 deque로 만들고, FIFO 순서대로 하나씩 꺼내 처리한 뒤 처리 순서를 리스트로 출력하세요.
  2. maxlen=5인 deque에 1부터 10까지 차례로 넣었을 때 최종 deque 상태를 예측하고, 왜 그렇게 되는지 설명하세요.
  3. 라운드로빈 할당을 흉내 내세요. 작업자 ['w1','w2','w3'] deque에서 rotate(-1)를 사용해 7개의 작업이 누구에게 배정되는지 순서를 구하세요.

이전 강의 정답

  1. heapq로 최소값 3번 꺼내기
>>> import heapq
>>> data = [7, 2, 9, 1, 5]
>>> heapq.heapify(data)
>>> [heapq.heappop(data) for _ in range(3)]
[1, 2, 5]
  1. Top-2 큰 값 구하기
>>> import heapq
>>> scores = [81, 95, 77, 88, 99]
>>> heapq.nlargest(2, scores)
[99, 95]
  1. 우선순위(숫자 작을수록 높음) 작업 처리
>>> import heapq
>>> pq = []
>>> heapq.heappush(pq, (2, "email"))
>>> heapq.heappush(pq, (1, "pager"))
>>> heapq.heappush(pq, (3, "batch"))
>>> [heapq.heappop(pq) for _ in range(3)]
[(1, 'pager'), (2, 'email'), (3, 'batch')]

실습 환경/재현 정보

  • 실행 환경: conda env python100 (Python 3.11.14)
  • 가정한 OS: macOS/Linux 공통
  • 예제 실행 방식: 터미널에서 python REPL 또는 ipython
  • 검증 포인트: deque, appendleft, popleft, maxlen, rotate 동작 확인