2. 큐(Queue) | II단원

🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)

큐 = 대사·이벤트가 나온 순서대로 처리될 때 씁니다. 대사 한 줄이 enqueue되고, 화면에 띄울 때마다 dequeue해서 "다음 대사"가 나와요. 어노잉 도그 대사가 선택지 전에 순서대로 나오는 그 구조가 큐예요.

큐(Queue, 큐)

큐는 줄 서기와 똑같아요. 먼저 줄 선 사람이 먼저 나갑니다. 영어로 FIFO(파이포)(First In First Out, 퍼스트 인 퍼스트 아웃) = "먼저 들어간 게 먼저 나온다"라고 해요.

큐: 뒤(rear)에 넣고, 앞(front)에서 뺀다. FIFO.

게임에서 대사·이벤트가 순서대로 나가게 할 때 큐를 씁니다. 프린터 대기, BFS(비에프에스, 너비 우선 탐색) 등에도 써요.

우선순위 큐는 급한 것(우선순위 높은 것)부터 꺼내는 큐예요. 시험에 나올 수 있어요.

📌 이론(알고리즘) ↔ 파이썬 함수

큐 연산 enqueue(뒤에 넣기) → deque.append(값) | dequeue(앞에서 꺼내기) → deque.popleft()

대응 큐는 "맨 뒤에 넣고, 맨 앞에서 뺀다"가 핵심이에요. 파이썬에서는 collections.deque(덱)를 쓰면 이 두 연산이 모두 빠릅니다.

from collections import deque / deque(리스트): 표준 라이브러리 deque(double-ended queue)는 앞·뒤 모두에서 O(1)로 넣고 뺄 수 있어요. 큐처럼 "뒤에 넣고 앞에서 뺄 때" 쓰기 좋습니다.
덱.append(값): 맨 뒤에 넣기 → enqueue(인큐)에 대응해요.
덱.popleft(): 맨 앞에서 하나 꺼내서 반환 → dequeue(디큐)에 대응해요. 이름에 "left"가 들어간 이유는 "앞쪽=왼쪽"이라고 보기 때문이에요.

왜 list가 아니라 deque인가요? 일반 리스트에서 pop(0)(맨 앞 제거)을 쓰면, 뒤의 값들을 한 칸씩 당겨야 해서 비용이 커요. deque는 맨 앞·맨 뒤만 다루도록 구현돼 있어서 큐 연산에 맞습니다.

📌 큐 — Python / C# / C++ 대응

연산	Python	C#	C++
뒤에 넣기 (enqueue)	`deque.append(x)`	`queue.Enqueue(x);` (`Queue<T>`)	`q.push(x);` (`queue<T>`)
앞에서 꺼내기 (dequeue)	`deque.popleft()`	`queue.Dequeue();`	`q.pop();` (앞에서 제거, 값은 `front()`로 먼저 확인)

응용 대사·이벤트 순서(한 줄씩 enqueue → "다음" 누르면 dequeue), BFS(III단원 그래프)에서 "가까운 정점부터" 탐색할 때 큐에 이웃을 넣고 앞에서 꺼내요. 프린터 대기열, 작업 스케줄링에도 씁니다.

😄 조크 큐에 줄 서 있는 사람한테 "뒤로 가세요" 하면? … 그게 바로 dequeue예요. 더 보기 →

큐에서 맨 앞에서 꺼낼 때 쓰는 메서드? (파이썬 deque)

out = q._____()

🐍 파이썬 (바로 실행)

🟨 자바스크립트로 확인

var q = ['첫번째', '두번째', '세번째'];
console.log('큐:', q);
var out = q.shift();
console.log('shift() →', out);
console.log('남은 큐:', q);

1, 2, 3을 순서대로 enqueue(인큐)한 뒤 dequeue(디큐) 두 번 하면 나오는 값은?

정답: 1, 2

풀이 단계

왜 1, 2인가요? 큐는 FIFO(먼저 들어간 것이 먼저 나옴)라서, 먼저 넣은 1이 먼저, 그다음 2가 나옵니다.

한 줄 요약 큐에서는 항상 "맨 앞에서만" 꺼내므로, 넣은 순서대로 나옵니다. 더 많은 예제 →

enqueue A → enqueue B → dequeue → enqueue C → dequeue 순서로 했을 때, 지금까지 꺼낸 값은?

답 보기

정답: A, B (꺼낸 순서)

풀이 enqueue A, B → 큐 [A, B]. dequeue → A 나옴(첫 번째로 꺼낸 값). enqueue C → 큐 [B, C]. dequeue → B 나옴(두 번째로 꺼낸 값). 따라서 지금까지 꺼낸 값은 A, B입니다.

풀어 본 뒤 정답을 펼쳐 확인하세요.

도전 1. 대사 큐에 "안녕!", "선택지가 있어요", "1. 예 2. 아니오"를 순서대로 enqueue한 뒤, dequeue를 두 번 했을 때 화면에 나온 두 줄은? 그리고 큐에 남은 것은?

정답 보기

나온 두 줄: "안녕!", "선택지가 있어요" (FIFO이므로 먼저 넣은 것부터)

큐에 남은 것: "1. 예 2. 아니오" 한 개. 게임에서 "다음" 버튼을 두 번 눌렀을 때와 같은 상황이에요.

도전 2. 스택과 큐의 공통점과 차이를 한 줄씩 쓰면? (넣고 빼는 위치)

정답 보기

공통점: 모두 "순서가 있는" 자료를 한 줄로 다룬다.

차이: 스택은 맨 위에서만 넣고 빼므로 LIFO. 큐는 맨 뒤에 넣고 맨 앞에서 빼므로 FIFO.

위 실습은 이 강의(큐)에서 배운 enqueue·dequeue, 즉 append·popleft를 쓰는 예제입니다. 손으로 해보려면 실습: 큐 (손으로 하기).