yeolyi.com성열의 컴퓨터공학

큐

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

프린터에 문서 세 개를 차례로 보내면 보낸 순서대로 인쇄되어야 합니다. 기다리는 문서를 스택에 담아 두면 마지막에 보낸 문서부터 나옵니다. 먼저 넣은 것을 먼저 꺼내는 자료구조가 필요합니다.

줄 서기

은행 창구 앞의 줄을 생각해 봅시다. 새로 온 사람은 맨 뒤에 서고, 창구는 맨 앞 사람부터 부릅니다.

이처럼 한쪽 끝에서 넣고 반대쪽 끝에서 꺼내는 자료구조를 큐(queue)라 합니다. 먼저 들어간 것이 먼저 나오므로 FIFO(First In, First Out)라고도 합니다. 꺼낼 쪽을 앞(front), 넣을 쪽을 뒤(rear)라 부릅니다.

스택처럼 배열로 만들어 봅시다. 값을 0번 칸부터 넣고, 꺼낼 때는 늘 0번 칸에서 꺼냅니다. 앞을 늘 0번 칸에 두려면 꺼낼 때마다 남은 값을 한 칸씩 당겨야 합니다.

배열 6칸 (위: 인덱스)
0앞·뒤
1
2
3
4
5
꺼낸 순서

개수 0 · 옮긴 값 0개

넣기를 몇 번 누른 뒤 꺼내기를 누르며 옮긴 값의 수를 봅시다.

값이 1000개 있으면 하나를 꺼낼 때마다 999개를 옮겨야 합니다.

앞과 뒤 번호

값을 당기는 대신 앞과 뒤가 몇 번 칸인지를 숫자로 기억하면 어떨까요? 꺼낼 때는 앞 칸을 읽고 앞을 한 칸 옮기고, 넣을 때는 뒤 칸에 쓰고 뒤를 한 칸 옮깁니다.

배열 6칸 (위: 인덱스)
0앞·뒤
1
2
3
4
5
꺼낸 순서

개수 0

넣기를 네 번, 꺼내기를 두 번 누른 뒤 넣기를 계속 눌러 봅시다.

꺼낸 앞쪽 칸이 비어 있는데도 쓰지 못합니다. 빈칸을 다시 쓸 방법은 없을까요?

원형 버퍼

배열의 끝과 처음을 이어 붙였다고 생각해 봅시다. 앞이나 뒤가 마지막 칸을 넘어가면 0번 칸으로 돌아갑니다. 이렇게 배열을 고리처럼 쓰는 방식을 원형 버퍼(circular buffer)라 합니다.

돌아가는 계산은 나머지 연산으로 합니다. 칸이 6개라면 5 다음은 (5 + 1) mod 6 = 0입니다. 뒤 칸 번호를 rear에 담아 코드로 쓰면 이렇습니다.

1#include <stdio.h>
2
3int main(void) {
4 int rear = 0;
5 for (int step = 0; step < 8; step++) {
6 printf("%d\n", rear);
7 // 5 다음은 0
8 rear = (rear + 1) % 6;
9 }
10 return 0;
11}

변수 없음
출력 없음

앞과 뒤를 모두 이렇게 옮기면 꺼낸 앞쪽 칸을 다시 씁니다.

배열 6칸을 고리로 (안쪽 숫자: 인덱스)0앞·뒤12345
꺼낸 순서

개수 0

  1. 넣기를 네 번, 꺼내기를 세 번 눌러 봅시다.
  2. 여섯 칸이 모두 찰 때까지 넣어 봅시다.

꽉 차면 앞과 뒤가 같은 칸을 가리킵니다. 큐가 비었을 때도 같은 칸을 가리키니, 담긴 값의 개수를 따로 세어 둡니다.

덱

앞에서도 넣고 뒤에서도 빼고 싶을 때가 있습니다. 앞과 뒤 양쪽에서 넣고 빼는 줄을 덱(deque)이라 합니다. 원형 버퍼에서 앞 번호를 1 줄여 그 칸에 넣으면 되니, 덱도 넣고 뺄 때마다 한 칸만 건드립니다. 한쪽만 쓰면 스택, 넣기와 빼기를 다른 쪽에서 하면 큐가 됩니다.

도전 문제

칸이 8개인 원형 버퍼로 큐를 만듭니다. 넣기와 꺼내기는 글과 같지만, 담긴 값의 개수를 세는 변수를 따로 두지 않고 앞과 뒤 두 칸 번호만 보고 큐가 비었는지 꽉 찼는지 판단하려 합니다. 그러려면 큐에 한 번에 담는 값을 많아야 몇 개로 제한해야 할까요? 숫자로 답하세요.