7강 / 20강

큐와 덱 — 먼저 온 사람이 먼저

줄 서기, 그리고 앞뒤로 다 되는 줄

급식실 줄을 새치기하면 어떻게 되나요? 난리가 나죠. 먼저 온 사람이 먼저 받는다는 규칙이 FIFO(First In, First Out)이고, 이 규칙의 자료구조가 큐(queue)입니다.

📚 스택 (LIFO)

넣는 곳과 빼는 곳이 같은 쪽
마지막에 넣은 것이 먼저
되돌아가기 · 실행 취소

🚶 큐 (FIFO)

넣는 곳과 빼는 곳이 반대쪽
먼저 넣은 것이 먼저
순서 지키기 · 대기열

프린터 인쇄 대기열, 게임 매칭 대기줄, 고객센터 상담 순서 — 전부 큐입니다.

고등학생먼저 온 사람이 먼저

스택의 정반대가 큐입니다.

먼저 넣은 것을 먼저 꺼낸다 — FIFO

	스택	큐
넣는 곳	뒤	뒤
꺼내는 곳	뒤	앞
성격	되돌아간다	차례를 지킨다

꺼내는 곳이 한 글자 다를 뿐인데 성격이 반대다

비유 — 매표소 줄

줄을 서면 먼저 온 사람이 먼저 삽니다. 당연하죠. 그게 공정하니까요.

스택이라면 나중에 온 사람이 먼저 산다 — 새치기

큐가 쓰이는 곳

어디	왜 큐인가
프린터 대기열	보낸 순서대로
고객 상담	공정해야 한다
메시지 처리	순서가 뜻을 가진다
BFS	가까운 곳부터 (15강)

"차례" 나 "가까운 것부터" 가 필요하면 큐다

15강 예고

미로를 탐색할 때 —

자료구조	결과
큐	가까운 곳부터 넓게 (BFS)
스택	한 방향으로 깊게 (DFS)

같은 코드에서 한 줄만 바꾸면 성격이 통째로 바뀐다

리스트로 만든 큐 — 동작은 맞지만, 문제가 하나 있습니다.

Python 브라우저에서 실행

줄 = []

줄.append("민준")        # 뒤로 들어오기 (enqueue)
줄.append("서연")
줄.append("지호")
print("줄:", 줄)

print("입장:", 줄.pop(0))   # 앞에서 나가기 (dequeue)
print("입장:", 줄.pop(0))
print("남은 줄:", 줄)

고등학생리스트로 만든 큐는 느립니다

note 의 경고가 2강의 밀림과 이어집니다.

리스트의 맨 앞을 빼면 전부 밀린다

숫자로

동작	움직이는 칸
`append` (뒤에 넣기)	0개 ✔
`pop()` (뒤에서 빼기)	0개 ✔
`pop(0)` (앞에서 빼기)	전부 ⚠

스택은 뒤만 쓰니 빠르고, 큐는 앞을 쓰니 느리다

얼마나 느린가

n개를 큐로 처리하면 —

개수	총 이동	체감
1,000	50만	순간
100,000	50억	수십 초

n² 이다 — 개수가 100배면 시간은 1만 배 (19강)

해결 — deque

from collections import deque
q = deque()
q.append(x)      # 뒤에 넣기
q.popleft()      # 앞에서 빼기 — 즉시 ✔

deque 는 양끝 모두 즉시 처리한다

어떻게 가능한가

8강의 연결 리스트와 비슷한 방식이에요. 칸이 딱 붙어 있지 않아서 밀 필요가 없습니다.

	리스트	deque
배치	딱 붙어 있다	덩어리로 나뉘어 있다
앞에서 빼기	전부 민다	앞 덩어리만 손댄다
번호로 접근	즉시	조금 느리다

또 그 맞바꿈 — 양끝을 얻고 중간 접근을 조금 내준다

큐로 쓸 때는 중간을 안 보니까 손해가 없죠.

쓰임에 맞는 그릇을 고르면 손해가 손해가 아니다

deque — 양쪽 끝이 모두 빠른 줄

collections.deque(데크, double-ended queue)는 맨 앞과 맨 뒤 모두 즉시 넣고 뺄 수 있게 만들어진 자료구조입니다. 8강에서 배울 연결 리스트와 비슷한 방식으로 만들어져서, 밀어내기가 아예 일어나지 않아요.

deque 는 앞뒤 네 가지 동작이 전부 빠릅니다.

Python 브라우저에서 실행

from collections import deque

줄 = deque(["민준", "서연", "지호"])

줄.append("하윤")          # 뒤에 추가
줄.appendleft("🔥응급")     # 앞에 추가 — 리스트에서는 느렸던 그 작업!
print(줄)

print("앞에서:", 줄.popleft())   # 앞에서 꺼내기 — 즉시
print("뒤에서:", 줄.pop())       # 뒤에서 꺼내기 — 즉시
print(줄)

🎮 줄 서기 실험실 — 속도까지 재 봅니다

사람을 줄에 세우고 빼면서 큐가 어떻게 도는지 보세요. 아래쪽 속도 대결 버튼을 누르면 list.pop(0) 과 deque.popleft() 의 차이가 숫자로 나옵니다.

고등학생덱 — 앞뒤로 다 되는 줄

덱(deque)은 양쪽 끝에서 넣고 뺄 수 있습니다.

스택도 되고 큐도 된다 — 둘을 포함한다

쓰는 법	되는 것
append + pop	스택
append + popleft	큐
넷 다	덱

그럼 항상 덱을 쓰면 되나

거의 그렇습니다. 다만 번호로 접근이 조금 느려요.

필요한 것	고를 것
번호로 자주 접근	리스트
양끝에서 넣고 빼기	덱

중간을 볼 일이 없으면 덱이 낫다

덱이 특히 유용한 곳 — 최근 N개

최근 = deque(maxlen=5)
최근.append(x)      # 5개를 넘으면 앞이 자동으로 빠진다

길이 제한을 걸면 오래된 것이 저절로 사라진다

쓰임	예
최근 검색어	최근 10개만
이동 평균	최근 20개의 평균
실행 취소	최근 50단계만

비유 — 회전문과 양방향 문

문	비유
한쪽만 열리는 문	스택 · 큐
양쪽으로 열리는 문	덱

가능성이 넓다고 항상 좋은 것은 아니다

제한이 있으면 실수를 막아 줍니다. 스택으로 쓸 자리에 덱을 쓰면 실수로 앞에서 꺼낼 수도 있죠.

"할 수 있는 일" 을 줄이는 것도 설계다

3만 명 줄을 다 빼는 데 걸리는 시간. 직접 재 봅니다.

Python 브라우저에서 실행

import time
from collections import deque

N = 30000

ㄹ = list(range(N))
시작 = time.time()
while ㄹ:
    ㄹ.pop(0)
리스트시간 = time.time() - 시작

ㄷ = deque(range(N))
시작 = time.time()
while ㄷ:
    ㄷ.popleft()
덱시간 = time.time() - 시작

print(f"list.pop(0)     : {리스트시간*1000:8.1f} ms")
print(f"deque.popleft() : {덱시간*1000:8.1f} ms")
print(f"→ deque 가 약 {리스트시간/max(덱시간,1e-9):.0f}배 빠릅니다")
print()
print("N을 2배로 늘리면 list 는 4배 느려지고, deque 는 2배만 느려집니다.")

고등학생왜 4배일까요

note 가 속도 차이를 재 봅니다. 숫자가 나오면 감이 확 옵니다.

차이는 고정된 배수가 아니다 — 개수에 따라 벌어진다

이게 중요한 이유

차이의 종류	의미
4배 고정	참을 만하다 — 상수배
개수에 비례	언젠가 못 쓴다 ⚠

19강의 핵심 — 상수배와 차수는 다른 문제다

숫자로 보면

개수	리스트 큐	deque	배수
1,000	0.05ms	0.03ms	2배
10,000	3ms	0.3ms	10배
100,000	300ms	3ms	100배

작을 땐 차이가 안 보이다가 커지면 터진다

이게 가장 무서운 유형의 문제입니다

때	보이는 것
개발 · 테스트	자료가 적어 빠르다
운영	자료가 많아 느리다

테스트를 통과하고 실전에서 죽는다

비유 — 짐 나르기

방법	10개	1000개
한 번에 여러 개	빠르다	빠르다
하나 나르고 다시 돌아옴	비슷하다	하루 종일

적은 양에서는 방법이 안 드러난다

그래서 성능 시험은 실제 규모로 해야 합니다. "10개로 해 보니 빠르던데" 는 증거가 아니에요.

덱(deque)은 스택도 되고 큐도 됩니다

양쪽 끝이 다 열려 있으니, 어느 쪽으로 넣고 어느 쪽으로 빼느냐만 정하면 됩니다.

쓰고 싶은 것	넣기	빼기
스택 (LIFO)	`append()`	`pop()` — 같은 쪽
큐 (FIFO)	`append()`	`popleft()` — 반대쪽
덱 (양쪽)	`append()` / `appendleft()`	`pop()` / `popleft()`

15강에서 미로를 탐색할 때, 같은 코드에서 이 한 줄만 바꿔 BFS와 DFS를 오가게 됩니다.

덱의 양쪽 끝을 동시에 쓰는 대표적인 예.

Python 브라우저에서 실행

from collections import deque

# 회문(앞뒤가 같은 말) 검사 — 양쪽에서 동시에 좁혀 들어갑니다
def 회문인가(말):
    ㄷ = deque(글자 for 글자 in 말 if 글자 != " ")
    while len(ㄷ) > 1:
        if ㄷ.popleft() != ㄷ.pop():     # 앞과 뒤를 동시에 꺼내 비교
            return False
    return True

for 말 in ["기러기", "토마토", "다시 합창합시다", "자료구조"]:
    print(f"{말:10} → {'✅ 회문' if 회문인가(말) else '❌ 아님'}")

🤔 확인 문제

큐에 A, B, C 를 넣은 뒤 두 번 꺼내면 나오는 순서는?

🤔 확인 문제

파이썬 리스트로 큐를 만들면 안 되는 이유는?

해설 동작은 맞지만 느립니다. 큐가 클수록 심해져요. collections.deque는 밀어내기 없이 앞뒤를 모두 즉시 처리합니다.

🤔 확인 문제

deque 로 스택을 만들려면?