前回の授業でStack(LIFO)を説明したので、 今日はQueue(FIFO)を説明する。

待ち行列Queue

待ち行列(Queue)は、FIFO(First In First Out)を配列で実装する場合、 一般的には、以下のようになる。 ただしエラー対策は記載していないので、要注意。

int que[ 100 ] ;
int wp = 0 ; // 書き込み用ポインタ
int rp = 0 ; // 読み出し用ポインタ
void put( int x ) {
que[ wp ] = x ;
wp = (wp + 1) % 100 ; // 循環させる
}
int get() {
int ans = que[ rp ] ;
rp = (rp + 1) % 100 ; // 循環させる
return ans ;
}

このような配列の領域を使い切ったら、先頭から再利用するような方法は、 リングバッファなどと呼ばれる。 このような待ち行列は、キー入力バッファや、プロセス待ち行列などに よく利用される。 しかし、このプログラムでも、配列サイズ以上の データは保存できないので、 リストを用いる。

struct List* top = NULL ;
struct List** tail = &top ;
void put( int x ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() {
int ans = top->data ;
struct List* del = top ;
top = top->next ;
free( del ) ;
return ans ;
}

ただし、このプログラムは、 常に１件以上データがリストに入っている場合は 問題がないが、 get() を実行して、データ件数が０件になると、 tail の指す先が おかしくなるので注意が必要。

また、待ち行列では、先頭ポインタと末尾ポインタの２つが必要であるが、 リスト構造の末尾のNULLを、先頭データを指すようにする循環リストと する場合も多い。 特に、プロセス待ち行列を実装するときのラウンドロビン方式 などでは、 末尾まで処理が及んだ次は先頭に戻って処理を行うため、 循環リストは都合がいい。

集合と2進数

集合を扱うプログラムでもリスト構造はよく利用される。 しかし、対比のためにまずは、2進数を使った集合処理を考える。

// 数学的な集合計算
A = { 1,2,3,5,7 }
B = { 1,2,4,8 }
A∩B = { 1,2 } // 積集合
A∪B = { 1,2,3,4,5,7,8 } // 和集合
A-B = { 3,5,7 } // 差集合

この例のような数値の集合であれば、2進数を使ったテクニックで簡単。

int a = (1<<1) | (1<<2) | (1<<3) | (1<<5) | (1<<7) ;
int b = (1<<1) | (1<<2) | (1<<4) | (1<<8) ;
int a_cap_b = a & b ;
int a_cup_b = a | b ;
int n = 値 ;
// nがaに含まれるか？
if ( a & (1<<n) != 0 )
nがaに含まれる ;