リスト構造への簡単な処理の説明が終わっているので、本日は応用ネタ。

末尾追加

先週説明したリストの生成は、先頭挿入型であったため、データは挿入順序とは逆順にならぶ。 後の説明のキューにも関連するので、末尾追加型の処理も説明する。

struct List {
int  data ;
struct Lint* next ;
} ;
struct List* top = NULL ;
struct List** tail = &top ;
int x ;
while( scanf( "%d" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}

スタックとリスト

スタックは、局所変数のデータや関数の帰りアドレスなどの保管で使われるデータ領域で 使われているが、LIFO(Last In First Out)「最後に入れたデータを最初に取り出せる」 データ構造。配列を使って記述すれば、

int stack[ 100 ] ;
int sp = 0 ; // 機械語の説明であれば、領域末尾から使うんだけど...
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
int ans = stack[ --sp ] ;
return ans ;
}
void main() {
push( 1 ) , push( 2 ) ; push( 3 ) ;
printf( "%d" , pop() ) ;
printf( "%d" , pop() ) ;
printf( "%d" , pop() ) ;
}

しかし配列を使うと、そのサイズ以上のデータを覚えることはできない。そこで、リスト構造のお出まし。

struct List* stack = NULL ;
int push( int x ) {
stack = cons( x , stack ) ;
}
int pop() {
int ans = stack->data ; // データ0件のときの処理は別途書いてね。
struct List* del = stack ;
stack = stack->next ;
free( del ) ;
return ans ;
}

リストと待ち行列

リストとは反対に、FIFO(First In First Out)「最初に入れたデータを最初に取り出せる」タイプの データ構造ま待ち行列(Queue)と呼ばれる。配列を使って記述すれば、

int queue[ 100 ] ;
int wp = 0 ;  // 書き込み用のポインタ
int rp = 0 ;  // 読み出し用のポインタ
void put( int x ) {
queue[ wp ] = x ;  // wpが一周してrpに追いついたときの処理は別途書くこと。
if ( ++wp > 100 ) wp = 0 ;
}
int get() {
int ans = queue[ rp ] ;  // 同じくデータが0件(wpに追いついた)の処理も別途書くこと。
if ( ++ rp > 100 ) rp = 0 ;
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d" , get() ) ;
printf( "%d" , get() ) ;
printf( "%d" , get() ) ;
}

このような配列を使った待ち行列では、配列サイズを超えた場合に、すでにデータを読み出して 使われていない部分を再利用するために、ポインタを先頭に戻す。 このデータ構造は、先頭と末尾が巡回してつながっているようなイメージなので、 「リングバッファ」と呼ばれる。

しかしながら、このリングバッファも配列での実装だから、配列サイズの上限は超えられない。 これまたリスト構造が便利なはず。

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