キュー は行列のことで、先に並んだ人が先に出てくる「先入れ先出し」のデータ構造です（キューの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 関数の内容を考えてみてください。

[ 関連記事 ] キュー（待ち行列）

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