큐와 덱: 공정함과 양 끝

"스택은 성급해서 방금 온 사람부터 챙겨. 큐는 가장 오래 기다린 사람부터 챙기고. 사람을 상대하는 시스템은 대개 뒤쪽을 원하지."

먼저 들어온 게 먼저 나간다

큐는 도착한 순서대로 처리해. enqueue는 뒤에 붙이고 dequeue는 앞에서 빼내니까 가장 오래된 항목이 먼저 나가지. FIFO는 계산대 줄이나 번호표처럼 선착순 정책을 받쳐주는 구조야. 다만 우선순위와 작업 길이, 재시도 정책까지 얽힌 시스템에서 전체 공정성을 FIFO 하나가 보장해 주진 않아.

리스트 함정, 한 번 더

Python 리스트로 큐를 만들어 볼 수도 있어. enqueue는 append, dequeue는 pop(0). 돌아가긴 해. 그리고 dequeue마다 조용히 O(n)을 먹지. pop(0)이 인덱스 0을 메우려고 남은 원소를 전부 왼쪽으로 미니까. 여기에 진짜 작업량을 흘려보내면 큐가 슬그머니 O(n²)이 돼. 해결책은 collections.deque야. 정확히 이 용도로 만들어졌고 양쪽 끝이 O(1)이거든. 큐가 필요하면 반사적으로 deque로 가. 평범한 리스트는 애초에 맞지 않는 기계야.

덱: 맥가이버 칼 버전

덱("deck", double-ended queue)은 앞뒤 양쪽에서 O(1)로 넣고 뺄 수 있어. 그래서 상위 집합이라고 부르지. 한쪽 끝만 쓰면 스택이 되고, 반대 끝을 쓰면 큐가 되고, 양쪽을 다 쓰면 슬라이딩 윈도우나 작업 훔치기 구조가 돼. Python의 deque는 고정 크기 블록을 연결 리스트로 엮어서 받치고 있어. 연결 구조가 배열을 정말로 이기는 자리가 있다고 연결 리스트 트랙에서 예고했던, 바로 그 자리야.

큐는 FIFO라서 가장 오래 기다린 항목을 먼저 꺼내. 선착순 정책을 받쳐줄 수는 있어도 시스템 전체의 공정성을 자동으로 보장하진 않아. 큐는 collections.deque로 만들어서 양 끝 O(1)을 챙기고, 숨은 O(n)인 list.pop(0)은 피해.

링 버퍼: 잊는 큐

deque(maxlen=N)은 길이가 정해진 덱이야. 용량을 넘겨서 넣으면 반대쪽 끝의 오래된 항목을 알아서 버려. 동작이 고정 용량 링 버퍼와 비슷해서 "마지막 N개만 유지"에 잘 맞아. 다만 Python이 이걸 전통적인 단일 원형 배열로 구현한다고 넘겨짚을 필요는 없어. 중요한 건 손으로 잘라내는 코드 없이 양 끝 연산을 O(1)에 준다는 계약이야.

피파의 고백

"최근 활동" 기능을 리스트로 만든 적이 있어. 이벤트를 append하고 [-100:]로 잘라서 마지막 100개만 남기는 식이었지. 돌아가긴 했는데 이벤트가 들어올 때마다 리스트를 새로 자르고 새로 복사하고 있었어. 아빠가 그걸 통째로 deque(maxlen=100)으로 바꿨어. 한 줄이고, 이벤트당 O(1)이고, 오래된 건 알아서 빠져. 내가 짜 넣은 잘라내기 로직 열 줄이 그대로 사라졌지. 맞는 구조를 고르니까 빨라지기만 한 게 아니라, 애초에 안 썼어도 될 코드가 지워지더라.

Code

큐, 링 버퍼, 그리고 스택으로 쓰는 덱·python

from collections import deque

# 큐를 제대로: 양 끝 O(1).
q = deque()
q.append("alice")      # enqueue (뒤로)
q.append("bob")
q.append("carol")
print(q.popleft())     # 'alice' — dequeue (앞에서), O(1)
print(q.popleft())     # 'bob'

# 왜 리스트는 안 돼: pop(0) 은 O(n) 이고 큐 반복문을 O(n^2) 으로 바꿔.
# (deque.popleft 은 O(1). list.pop(0) 은 전부 왼쪽으로 밀어.)

# 링 버퍼: 가장 최근 N 개만 유지, 오래된 것 자동 퇴출.
recent = deque(maxlen=3)         # 용량 3
for event in ["login", "click", "scroll", "buy", "logout"]:
    recent.append(event)         # 용량 너머면 가장 오래된 게 조용히 떨어짐
print(list(recent))              # ['scroll', 'buy', 'logout'] — 마지막 3개만

# 덱은 스택도 될 수 있어 (한쪽 끝만 써):
stack = deque()
stack.append(1); stack.append(2)
print(stack.pop())               # 2 — LIFO, 같은 덱

Exercise

빠른 새로고침 남용을 잡으려고 마지막 페이지 로드 5건을 추적하려고 해. deque(maxlen=5)로 이걸 어떻게 구현할지 말이나 코드로 그려 보고, 새 로드 하나가 왜 O(1)인지 설명해. 그다음 같은 걸 리스트로, 그러니까 append한 뒤 list = list[-5:]로 처리하면 왜 낭비인지, 덱은 다시 잘라내는 대신 뭘 하는지도 짚어 봐.

Hint

deque(maxlen=5)는 append할 때 가장 오래된 항목을 자동으로 버리고 양 끝 연산을 O(1)에 해줘. 리스트 슬라이스는 매번 새 리스트를 만들고 원소 참조를 복사하지만, 덱을 쓰는 쪽은 그 복사 코드를 직접 짤 일이 없어. 그렇다고 내부 구현을 포인터 두 개짜리로 단순하게 단정하진 마.

먼저 들어온 게 먼저 나간다

리스트 함정, 한 번 더

덱: 맥가이버 칼 버전

링 버퍼: 잊는 큐

피파의 고백

Code

External links

Exercise

Progress

댓글 0