큐와 덱: 공정함과 양 끝

"스택은 성급해 — 마지막에 온 사람을 모셔. 큐는 공정해 — 가장 오래 기다린 사람을 모셔. 사람을 건드리는 대부분 시스템은 공정한 쪽을 원해."

먼저 들어온 게 먼저 나간다

큐는 도착 순으로 모셔: enqueue 는 뒤에 추가, dequeue 는 앞에서 제거, 가장 오래된 항목이 늘 먼저 가. 시간에 따른 공정함의 구조야 — 계산대 줄, 인쇄 작업, 번호표 시스템, 작업 스케줄러. "선착순" 이 맞는 정책인 어디든, 밑에 큐가 깔려.

리스트 함정, 한 번 더

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) push 와 pop 을 허용해. 그래서 상위집합이야: 한쪽만 쓰면 스택; 반대 끝을 쓰면 큐; 양쪽을 자유롭게 쓰면 슬라이딩 윈도우나 작업-훔치기 구조. Python 의 deque 는 고정 크기 블록의 연결 리스트가 받쳐 — Linked Lists 트랙이 약속한, 연결 구조가 배열을 진짜로 이기는 바로 그 자리야.

큐는 FIFO (공정, 오래된 것 먼저). collections.deque 로 지어 양 끝 O(1) — pop(0) 쓰는 리스트는 절대, 그건 숨은 O(n²). 덱은 스택과 큐 둘 다 일반화해.

링 버퍼: 잊는 큐

아름다운 특수 케이스: deque(maxlen=N) 은 고정 크기 링 버퍼야. 용량 너머로 push 하면 가장 오래된 항목이 반대쪽 끝으로 조용히 떨어져. "마지막 N 개만 유지" 에 완벽해 — 최근 100 로그 줄, 센서 읽기의 롤링 윈도우, 마지막 50 채팅 메시지. 수동 자르기 없음, 성장 없음, push 당 O(1). 큐이면서 잊는 기계고, 스트리밍이랑 모니터링 코드에 끊임없이 나타나.

피파의 고백

난 "최근 활동" 기능을 리스트로 지어, 이벤트를 append 하고 [-100:] 슬라이싱으로 마지막 100 개를 유지했어. 작동했지만, 매 이벤트가 리스트를 다시 슬라이싱하고 다시 복사했어. 아빠가 전체를 deque(maxlen=100) 으로 바꿨어 — 한 줄, 이벤트당 O(1), 오래된 것 자동 퇴출. 내 자르기 로직 열 줄이 사라졌어. 맞는 구조는 속도만 올린 게 아니라; 내가 애초에 안 써도 됐을 코드를 지웠어.

Code

큐, 링 버퍼, 그리고 덱-as-스택·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) 이고 가장 오래된 걸 자동 떨굼. 리스트 접근은 매번 최대 5 원소를 새 리스트로 다시 복사해 (그리고 슬라이스가 쓰레기를 만듦); 덱은 내부 포인터 둘만 옮겨 — 복사 없음.

먼저 들어온 게 먼저 나간다

리스트 함정, 한 번 더

덱: 맥가이버 칼 버전

링 버퍼: 잊는 큐

피파의 고백

Code

External links

Exercise

Progress

댓글 0