先週の授業で、リストへの挿入・追加処理について説明したので、 今日はその応用で、リストを用いたスタックと待ち行列(Queue)の説明を行う。 また、今週は公開授業週間ということで、他の先生の見学もあって、ちょっと緊張。

スタック

配列を用いた、LIFO(Last In First Out)=スタックであれば、一般的に 以下のようなコードになる。

int stack[ 100 ] ;
int sp = 0 ;
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
return stack[ --sp ] ;
}

しかし、この方法では、配列サイズ以上のデータは保存できない。 これをリストを使うことでサイズを気にしないスタックを実現できる。

struct List* stack = NULL ;
void push( int x ) {
stack = cons( x , stack ) ;
}
int pop() {
int ans = stack->data ;
struct List* del = stack ;
stack = stack->next ;
free( del ) ;
return ans ;
}

キュー

待ち行列(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を、先頭データを指すようにする循環リストと する場合も多い。特に、プロセス待ち行列を実装するときのラウンドロビン方式 などでは、末尾まで処理が及んだ次は先頭に戻って処理を行うため、 循環リストは都合がいい。