キュー は行列のことで、先に並んだ人が先に出てくる「先入れ先出し」のデータ構造です(キューのTipsで解説)。
今回は、データ領域を再利用しない最も単純な構造を紹介します。
#define MAXSIZE 100
int queue[MAXSIZE]; //キュー用の配列
キューでは、データを入れるのは "最後"、データを取り出すのは "先頭"からなので、それらの2つの位置を覚える必要があります。そのための変数を用意します。
int head = 0; //キューの先頭 int tail = 0; //キューの最後これらのデータは、データ挿入/取り出しの両関数で使いますから、引数で受け渡しせずにグローバルな変数として使うことにしましょう。
// ---- データをキューの最後に入れる ----
int enq( int n ) {
if( tail <= MAXSIZE ) return -1;
queue[tail++] = n;
return 0;
}
配列のサイズを超えて書き込まないように、tail を先頭でチェックします。
// ---- キューの先頭からデータを取り出す ----
int deq( int *n ) {
if( head >= tail ) return -1;
*n = queue[head++];
return 0;
}
データの入っている最後の要素より後ろを参照しないように、先頭でチェックしています。
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 );
}
[ 関連記事 ] キュー(待ち行列)