Lesson 11 of 20

주문 큐 — 밀려드는 일을 순서대로 처리하기

선착순이 공정할까? 급한 주문은 어떻게 하지?

오전 10시, 타임세일이 시작됐습니다. 1분에 3,000건의 주문이 들어오는데, 서버는 1분에 800건밖에 처리하지 못합니다.

이때 선택지는 셋입니다.

거절한다 — "잠시 후 다시 시도해 주세요" (손님이 떠남)
기다리게 한다 — 대기열에 넣고 순서대로 처리 ✅
그냥 다 받는다 — 서버가 죽음 💀

정답은 두 번째, 큐(queue)입니다.

High school선착순이 공정할까

주문이 몰려들면 순서대로 처리해야 합니다. 그 줄이 큐(queue) 예요.

큐 = 먼저 온 사람이 먼저 (FIFO)

일상에서

매표소 줄, 은행 번호표, 학교 급식 줄 — 전부 큐입니다. 새치기가 없는 구조죠.

동작	어디서
넣는다 (enqueue)	줄 뒤에
꺼낸다 (dequeue)	줄 앞에서

양쪽 끝을 다르게 쓴다 — 그게 큐의 정의

그런데 선착순이 늘 공정한가

부제가 그걸 묻습니다.

결제 완료 주문과 장바구니 담기 가 같은 줄에?
구급차가 신호를 기다려야 하나?

급한 일이 있으면 우선순위가 필요하다

그래서 우선순위 큐가 나옵니다. 다만 거기에도 함정이 있어요 — 굶주림입니다.

High school큐 = 먼저 온 사람이 먼저

note 를 조금 더 봅시다. 큐와 스택의 차이예요.

	큐 (FIFO)	스택 (LIFO)
꺼내는 곳	앞에서	뒤에서
비유	줄 서기	접시 쌓기
쓰임	작업 처리 · BFS (15강)	되돌리기 · DFS (15강)

넣는 곳은 같고 꺼내는 곳만 다르다

스택의 예 — 되돌리기

문서 편집기의 Ctrl+Z 를 생각해 보세요. 가장 최근 것부터 되돌립니다.

먼저 한 일을 먼저 되돌리면 이상하죠. 그래서 스택이에요.

큐의 예 — 프린터

프린터에 여러 사람이 인쇄를 보내면 보낸 순서대로 나옵니다.

나중에 보낸 게 먼저 나오면 불공정하죠. 그래서 큐입니다.

공정함이 중요하면 큐, 최근이 중요하면 스택

그리고 15강에서 다시 만납니다

그래프를 훑을 때 —

자료구조	탐색 방식
큐	BFS — 넓게 퍼져 나간다
스택	DFS — 깊게 파고든다

자료구조 하나 바꾸면 알고리즘이 바뀐다

deque 는 앞뒤 모두 O(1). 리스트의 pop(0)은 O(n)이라 큐에 부적합합니다.

Python Runs in your browser

from collections import deque

주문큐 = deque()

# 1분에 주문 6건이 들어옴
for i in range(1, 7):
    주문큐.append(f"주문{i:02d}")
print("대기열:", list(주문큐), f"({len(주문큐)}건 대기)")

# 서버는 1분에 2건만 처리 가능
for _ in range(2):
    처리중 = 주문큐.popleft()          # 맨 앞에서 꺼냄
    print("  처리 완료 →", 처리중)

print("남은 대기열:", list(주문큐), f"({len(주문큐)}건)")
print()
print("💡 대기열이 계속 쌓이면? 그것이 '장애'의 신호입니다.")

High schoollist.pop(0) 을 큐로 쓰지 마세요

note 가 숨은 O(n²) 하나를 짚습니다. 3강에서 예고했던 그것이에요.

list.pop(0) 은 O(n) 이다

왜 그런가

리스트에서 맨 앞을 빼면 나머지가 전부 앞으로 밀려야 합니다.

동작	비용
`pop()` — 맨 뒤	O(1) — 그냥 뺀다
`pop(0)` — 맨 앞	O(n) — 전부 민다

앞에서 빼면 10,000개가 한 칸씩 움직인다

비유 — 줄 맨 앞 사람이 나가면

극장 좌석에 번호가 붙어 있다고 합시다. 1번 사람이 나가면 모두가 한 칸씩 옮겨 앉아야 해요.

2번이 1번으로, 3번이 2번으로… 100명이면 99번 이동입니다.

반복문 안에서 하면 O(n²) 이 된다

해결 — deque

파이썬의 collections.deque 는 양쪽 끝 모두 O(1) 입니다.

	list	deque
뒤에 넣기	O(1)	O(1)
앞에서 빼기	O(n)	O(1) ✔

자료형 하나 바꿔서 n 배 빨라진다

9강의 리스트 → 집합 과 같은 이야기입니다 — 담는 그릇이 속도를 정해요.

같은 큐, 자료구조 하나 바꿨을 뿐인데.

Python Runs in your browser

import time
from collections import deque

N = 30000

# ❌ 리스트를 큐로 — pop(0) 은 O(n)
목록 = list(range(N))
t0 = time.time()
while 목록:
    목록.pop(0)
느림 = time.time() - t0

# ✅ deque — popleft() 는 O(1)
큐 = deque(range(N))
t0 = time.time()
while 큐:
    큐.popleft()
빠름 = time.time() - t0

print(f"❌ list.pop(0)     : {느림*1000:>8.1f} ms")
print(f"✅ deque.popleft() : {빠름*1000:>8.1f} ms")
print(f"→ 약 {느림/max(빠름,1e-9):,.0f} 배 차이")

선착순이 항상 공정할까요?

이런 상황을 생각해 봅시다. 대기열에 이런 일들이 섞여 있습니다.

일반 주문 500건
결제 취소 요청 3건 — 늦으면 고객 항의가 폭발합니다
서버 상태 점검 1건 — 이게 늦으면 장애를 못 알아챕니다

선착순으로 하면 결제 취소가 500건 뒤에 처리됩니다. 그래서 필요한 것이 우선순위 큐(priority queue)예요.

우선순위 큐 = 힙. 급한 일이 새치기하되, 동점이면 선착순.

Python Runs in your browser

import heapq

# (우선순위, 순번, 내용) — 숫자가 작을수록 급함
대기열 = []
순번 = 0

def 넣기(우선순위, 내용):
    global 순번
    heapq.heappush(대기열, (우선순위, 순번, 내용))
    순번 += 1

넣기(3, "일반 주문 A")
넣기(3, "일반 주문 B")
넣기(1, "🚨 결제 취소 요청")
넣기(3, "일반 주문 C")
넣기(2, "⚠️ 재고 부족 경보")
넣기(1, "🚨 서버 상태 점검")

print("처리 순서:")
while 대기열:
    우선, 순, 내용 = heapq.heappop(대기열)
    print(f"  [우선순위 {우선}] {내용}")

print()
print("💡 순번을 함께 넣은 이유: 같은 우선순위면 '먼저 온 순서'로 처리하기 위해 (7강 동점 처리!)")

🎮 주문 처리 대기열 시뮬레이터

주문 유입 속도와 서버 처리 속도를 조절해 보세요. FIFO와 우선순위 큐를 전환하면 급한 주문의 대기 시간이 얼마나 달라지는지 보입니다. 유입이 처리보다 빠르면 대기열이 폭발합니다 — 꼭 만들어 보세요.

High school굶주림 — 우선순위 큐의 함정

note 가 굶주림(starvation) 이라는 문제를 짚습니다. 이름부터 무섭죠.

우선순위가 낮은 일이 영원히 처리 안 되는 것

어떻게 일어나나

급한 주문을 먼저 처리하기로 했습니다. 좋은 생각이죠.

그런데 급한 주문이 계속 들어오면? 급하지 않은 주문은 영원히 기다립니다.

시각	큐 상태
10:00	[일반A] — 곧 처리되겠지
10:01	[급행1, 일반A]
10:02	[급행2, 일반A]
…	일반A 는 계속 뒤로

각 결정은 옳은데 전체 결과는 불공정하다

비유 — 응급실

응급실은 중증부터 봅니다. 옳은 정책이죠.

그런데 중증 환자가 계속 오면 가벼운 환자는 몇 시간을 기다립니다. 실제로 벌어지는 일이에요.

해결 — 기다린 만큼 우선순위를 올린다

에이징(aging) — 오래 기다릴수록 우선순위 상승

대기 시간	우선순위
0분	일반
10분	조금 올림
1시간	급행과 같아진다

언젠가는 반드시 처리된다는 보장을 만든다

운영체제의 프로세스 스케줄링도 같은 문제를 안고 있습니다. /os 강의에서 다시 만나요.

큐가 알려 주는 것 — 대기열 길이는 최고의 지표

시스템 관리자에게 대기열 길이는 체온계입니다.

대기열 상태	의미	조치
0에 가깝게 유지	여유 있음	정상
오르내리지만 결국 0	순간 몰림을 잘 흡수 중	정상
계속 늘어남	처리 속도 < 유입 속도	🚨 처리기 증설 · 유입 제한(17강)
꽉 차서 거절 발생	이미 장애	🚨 긴급 대응

"CPU 사용률 60%인데 서비스가 느려요"의 답이 대개 여기 있습니다. CPU가 아니라 큐를 보세요.

🤔 Check yourself

파이썬 리스트를 큐로 쓰면서 pop(0)을 쓰면 생기는 문제는?

Answer 리스트는 연속된 칸이라 앞을 빼면 전부 당겨야 합니다. collections.deque를 쓰면 양끝 모두 O(1)이에요.

🤔 Check yourself

우선순위 큐에 항목을 (우선순위, 순번, 내용) 형태로 넣는 이유는?

🤔 Check yourself

대기열 길이가 계속 늘어나기만 한다면 어떤 상태일까요?