Namaran

Code daily. Without assist.

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 のほうが先に処理されます。