2026-08-29
job_queue.c
#include <stdio.h>
int main(void) {
int queue[8] = {3};
int head = 0, tail = 1;
while (head < tail) {
int job = queue[head++];
printf("%d ", job);
if (job >= 2) {
queue[tail++] = job - 1;
queue[tail++] = job - 2;
}
}
printf("\n");
}
これは何を出力するでしょうか?
Answer
3 2 1 1 0 です(最後の 0 のあとに空白が1つ入ります)。
queue は、head の位置から取り出し、tail の位置へ足す配列です。取り出すのは常に一番前、足すのは常に一番後ろなので、仕事は足された順に処理されます。2以上の仕事 n は、処理されると n - 1 と n - 2 を後ろに足します。
最初は 3 だけが入っています。3 を処理すると後ろに 2 と 1 が並び、次に 2 を処理すると、その後ろに 1 と 0 が足されます。このとき列は 1 1 0 で、先頭の 1 は 3 が足したもの、後ろの 1 0 は 2 が足したものです。1 と 0 は何も足さないので、そのまま 1、1、0 の順に出力されて列が空になります。
2 が足した 1 と 0 を、2 の直後に処理されると読むと 3 2 1 0 1 になります。これは仕事を再帰呼び出しで片付けたときの順で、足された仕事がすぐに処理されます。キューに足された仕事は、それより前から待っている仕事の後ろに並ぶので、3 が足した 1 のほうが先に処理されます。