はじめての C

lang

C programming note*1

キュー queue は、先に 入れた データが 先に 取り出される データ構造 (First-In-First-Out) だ。

後から 入った データは いちばん 後ろに 追加される。

データが 入れられた 順に 処理されるのを 待つため 「待ち行列」とも いう。(p189)

キューの 実現は、モジュロ演算子を 使って、見かけ上の リングバッファを つくることで 可能に なります。

% は 剰余演算子 modulus operator、つまり 割算の 「余り」を 求める 演算子である。 たとえば "10 % 7" は 3 だ。 (ただし) 割られる数も 割る数も 整数型で なければならない。(p191)

キューで モジュロ演算子を 使って データを 入力する 関数は、次のような ものです。

int r_buf[MAX];

int sp = 0;

int cnt = 0;
void buf_in(int c)

{

    if (cnt == MAX)

        return;

    r_buf[(sp + cnt) % MAX] = c;

    ++cnt;

}
モジュロ演算子を 使った 割られるほうの数は 配列の添字に count数を 加えたもの、割るほうの数は 添字の 最大値です。 ここの ところ、
r_buf[(sp + cnt) % MAX] = c;
sp は このプログラムでは 変化しませんから、その値は (一応) 0 です。 プログラムを 使って 配列に 値を 入れていくと、cnt の 数は 増えていきますが、最大でも その値は "MAX -1" に なります。
値を 入力するだけなら、モジュロ演算子の 左辺は つねに 右辺の 値より 小さくなります。
このとき、モジュロ演算子が どんな ふるまいを するのか、実際に 試してみましょう。
/* modulus_1.c */

#include <stdio.h>
main()

{

    int a;

    int b;
    a = 7;

    b = 10;

    printf("%d\n", a % b);

    b = 20;

    printf("%d\n", a % b);
    return 0;

}
結果は、
7

7
と なるはずです。つまり、"a < b" の 場合には 剰余計算の 結果は 'b' の 値に 関係なく、つねに 'a' という 値に なるわけです。
(sp + cnt) % MAX == sp + cnt
と いうことですね。
では、今度は データを 次々 取り出していくと、どう なるのか ?
1つ データが 取り出されると 配列は 1つ ずれていくので、sp の 値は 最大 "MAX - 1" まで 増えるはずです。
途中で "sp + cnt" の 値は MAX の 値を 越えてしまいます。
ただし、最大でも "(sp + cnt) < (MAX * 2)" の 範囲に 収まります。
つまり この場合、剰余計算の 結果は、
(sp + cnt) % MAX == (sp + cnt) - MAX
と なるはずです。 試してみましょう、
/* modulus_2.c */

#include <stdio.h>
main()

{

    int a;

    int b;
    int a = 25;

    int b = 13;

    printf("%d\n", a % b);

    int b = 17;

    printf("%d\n", a % b);
    return 0;

}
コンパイルして 実行させるまでもなく、結果は、
12

8
と なります。
つまり 'b' が MAX の 値だとすると、配列は それぞれ 13 と 17 で 終わっているにも かかわらず、見かけ上では 'a' の 値が 12 (→ 25 - 13) 及び 8 (→ 25 - 17) と、一巡しているように 見えます。

概念的には、配列の 最後に 最初が つながったような リング状の データ構造となる。 これを リングバッファ ring buffer と 呼ぶ。

このように データ構造を リング状に することにより、データを 入れる 位置と 取り出す 位置を 無限に ずらし続けることが できる (ようになる)。(p191)

この仕組みを 取り入れることで、配列の 添字 sp と count 数とが どのように 変化しても、つねに 最初に 入れた 順から データを 取り出すことが できるのです。

キューを C で 実現するときには、1つの 配列と 2つの 指標用の 変数 (sp と cnt) を 用いて、次のように コーディングする。

int r_buf[MAX];

int sp = 0;

int cnt = 0;
void buf_in(int c)

{

    if (cnt == MAX)

        return;

    r_buf[(sp + cnt) % MAX] = c;

    ++cnt;

}
int buf_out(void)

{

    if (cnt == 0)

        return 0;

    r = r_buf[sp];

    sp = ++sp % MAX;

    return r;

}

データを 引数にして buf_in() 関数を 呼び出すことにより、データが キューに 格納される。

また、buf_out() 関数を 呼び出すことにより、戻り値として キューから データを 取り出すことが できる。(p190-191)

では、どのような ところで 使われているか、というと、

キューは、キーボードや マウスの 入力イベントを 処理する 場合など、ある程度の 先行入力を 蓄えておく 必要の あるときなどに よく 使われる。(p190)

*1:「作ってわかる Cプログラミング」