Thinkers'Studio
JavaとC言語の自習ツール
配列を使ったキューの例

 キュー は行列のことで、先に並んだ人が先に出てくる「先入れ先出し」のデータ構造です(キューのTipsで解説)。
 今回は、データ領域を再利用しない最も単純な構造を紹介します。

キューのデータ構造

 ここでは、次のような int配列にデータを入れます。
#define MAXSIZE 100
int queue[MAXSIZE]; //キュー用の配列
 キューでは、データを入れるのは "最後"、データを取り出すのは "先頭"からなので、それらの2つの位置を覚える必要があります。そのための変数を用意します。
int head = 0;       //キューの先頭
int tail = 0;       //キューの最後
 これらのデータは、データ挿入/取り出しの両関数で使いますから、引数で受け渡しせずにグローバルな変数として使うことにしましょう。

データを入れる操作( enqueue )

 引数で指定されたデータをキューの最後に追加します。 queue[tail] に代入し、tail をひとつずらす操作です。
// ---- データをキューの最後に入れる ----
int enq( int n ) {
    if( tail <= MAXSIZE ) return -1;

    queue[tail++] = n;
    return 0;
}
 配列のサイズを超えて書き込まないように、tail を先頭でチェックします。

データを取り出す操作( dequeue )

 データをキューの先頭から取り出し、引数に返します。 queue[head] の内容を返すことになります。
// ---- キューの先頭からデータを取り出す ----
int deq( int *n ) {
    if( head >= tail ) return -1;

    *n = queue[head++];
    return 0;
}
 データの入っている最後の要素より後ろを参照しないように、先頭でチェックしています。
 そして値を取り出したら、head をひとつ後ろにずらします。 データの取り出しといっても、実際に配列のデータを削除したりクリアしたりするわけではありません。 head が次の要素を指すようにするだけです。

データ領域の問題

 上記の方法だと、どんどんデータを追加していくと領域が足りなくなり、一方でデータを取り出した部分は「使わない領域」になってしまいます。 効率よく使うために、リングバッファと呼ばれる仕組みを使うことがあります。 これは、配列の先頭と最後がリング状につながっているかのように扱い、データ取り出し済みの領域を再利用する方法です(これはまた、別の機会に)。

main関数の例

 上記の内容を使ったプログラムの main の例です。
 キューの Tips で紹介した(平成25年秋期 基本情報技術者試験 午前問5)の操作をこのキューを使って行います。
main() {
    int     n;

    enq( 1 ); enq( 2 ); enq( 3 );
    if( deq( &n ) == 0 ) printf( " %d was dequeued.\n", n );
    enq( 4 ); enq( 5 );
    if( deq( &n ) == 0 ) printf( " %d was dequeued.\n", n );
    enq( 6 );
    if( deq( &n ) == 0 ) printf( " %d was dequeued.\n", n );
    if( deq( &n ) == 0 ) printf( " %d was dequeued.\n", n );
    //次に deq を行うと?
    if( deq( &n ) == 0 ) printf( "(正解) %d was dequeued.\n", n );
}

(今回のクイズ)
 上記の enq, deq 関数の最後に、キューに入っている有効なデータをプリントする prtQue 関数を呼び出そうと思います。 prtQue 関数の内容を考えてみてください。

[ 関連記事 ] キュー(待ち行列)


 前回、クイズはありませんでした。