リスト構造によるStackの続きの話しとして、リスト構造にてFIFOを作るプログラム の解説。

リストでqueue

最初に、配列を使ったFIFOのプログラムを示し、 (1)プログラムにリング操作となる処理の追加、 (2)read pointer がwrite pointer を追い抜くなどの対処の必要性を示す。 最終的に リングバッファ という名前を示し、実例としてキーボードなどの、 受け側が忙しい時の一時データ保管という意味合いを説明。 その後で,リストでFIFOの説明として、以下のコードを示す。

struct List* queue ; // 初期状態は最初伏せて説明
struct List** tail ;
void put( int x )
{   (*tail) = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get()
{   struct List*d = queue ;
int ans = queue->data ;
queue = queue->next ;
free( d ) ;
return ans ;
}

課題の提示

演習課題として、リスト構造のプログラム作成として、 (1) 文字列,(2)複素数,(3)名前と電話番号のいずれかのリスト構造を定義し、 (a) 先頭挿入型、(b)末尾追加型のいずれかの方法で入力データを保存し、 データ検索などの処理を行った後、全データを表示する。

データの途中への挿入・削除

void insert( struct List* p , int x )
{   struct List* n ;
n = (struct List*)malloc( sizeof( struct List ) ) ;
if ( n != NULL ) {
n->data = x ;
n->next = p->next ;
p->next = n ;
}
}
void del( struct List* p )  // 関数名にC++キーワードdeleteは避ける
{   struct List* d = p->next ;
p->next = d->next ;
free( d ) ;
}