図 12-7．insertTop 呼び出し直後
スタックは制限つきの連結リストである． スタックへの要素の挿入は先頭の位置に限られ，削除も先頭の要素に限られる． このため，スタックでは後に挿入されたデータから先に削除される． 前回掲載した最後のプログラム list12y6.c は先頭のみに挿入を行う リストであるから，これをベースにスタックを実現する．
スタックの先頭に要素を挿入する関数 insertTop を作り， list12y6.c を insertTop 関数を使う形に変更する． insertTop の引数としては，リストの先頭場所（スタックでは Top とよぶ） と挿入すべき要素の data フィールドの値が考えられる． list12y6.c では main 関数の startPtr にリストの先頭要素へのポインタが常に保持されている． 先頭要素へのポインタがわかればリストすべての内容に到達できるので， startPtr はリスト全体を表すと考える．具体的には あるリストを操作する関数の引数としてリストを渡すときに リストの先頭要素へのポインタ，場合によってはリスト先頭要素へのポインタへのポインタ を渡せばよいように設計する． 先頭へのポインタでリスト全体を表すのはリストを操作するプログラムの定石である． このプログラムでは要素が先頭に追加されるたびに startPtr の値が変わる． 関数 insertTop で要素の挿入を行うとき，main 関数の startPtr の値も 変更しなければならない． これは呼び出された関数が呼んだ側の値を変更する例の一つである．
呼び出された関数が呼んだ側の値を変更するにはポインタを利用する． 変えたい startPtr のポインタを insertTop に渡す仕様にすればよい． startPtr はポインタ変数であるが，変数である以上アドレスをもち， そのポインタを求めることができる． これがポインタへのポインタを利用する理由である．
結局，insertTop 関数は以下の 2 引数をとる void 型関数とする．
以下のプログラムの insertTop 関数の内容を書け． insertTop 関数は第一引数が指すポインタが指す要素を先頭とするリストに 対し，第二引数を data 部の値とする要素を先頭に挿入する． このとき第一引数が指すポインタは挿入後のリストの先頭を指すものとする．
/* 挿入を関数化する．*/
#include <stdio.h>
#include <stdlib.h>
struct listNode {
int data;
struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
void insertTop(LISTNODE **, int);
void printList(LISTNODE *);
main()
{
LISTNODE *startPtr, *currentPtr;
int value;
startPtr = NULL;
printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
scanf("%d", &value);
while (value >= 0) {
insertTop(&startPtr, value);
printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
scanf("%d", &value);
}
printList(startPtr);
return 0;
}
void insertTop(LISTNODE ** sPPtr, int data)
{
}
void printList(LISTNODE * cPtr)
{
while (cPtr != NULL) {
printf("%3d ", cPtr->data);
cPtr = cPtr->nextPtr;
}
putchar('\n');
}
list12x7.c
insertTop は下の図 12.7 から 図12.10 の処理を行う関数として実装すればよい． insertTop 呼び出し直後は仮引数 sPPtr へは startPtr へのポインタが渡されるため， 以下の状態になる．
図 12-7．insertTop 呼び出し直後
insertTop 内で malloc を利用して新しいリスト要素のための LISTNODE 型の領域を確保し，そのポインタを currentPtr へ格納する．
図 12-8．新しいリスト要素の領域を確保した直後
確保した新しいリスト要素の領域へ必要な値を格納する．
図 12-9．新しいリスト要素に値を格納した直後
リスト全体を表す変数として，常にリスト先頭要素へのポインタを main 関数の変数 startPtr に格納しておく必要がある．最後に startPtr の内容を新規要素のアドレスに変更する．これは関数 insertTop へリスト先頭要素へのポインタ ではなくリスト先頭要素へのポインタへのポインタを渡したからこそ可能なことである．
図 12-10．startPtr の値を変更し，挿入が完了した後
次にリストの先頭要素を削除する関数 deleteTop を作成する． deleteTop 関数は先頭要素をリストから削除し，その data 部の値を返り値とする関数である．リストの先頭要素 がいままで先頭だった要素から次の要素へ変わるため， 先頭要素へのポインタ startPtr の値を変更する必要がある． すなわち，insertTop と同様に先頭要素へのポインタへのポインタを リストを表す引数として与える必要がある．
結局，deleteTop は以下の 1 引数とをとる int 型関数とする．
deleteTop の戻り値は処理前に先頭にあった要素の data フィールドの値とする．
deleteTop で行うべき処理は， 破棄される古い 1 番目の 構造体のメモリ領域を free を使って解放することと， リスト全体を表す変数として常に先頭要素を指す変数 startPtr の内容を， 2 番目の要素を指すように変更するか，2番目がなければ NULL が格納されるようにすることである． 手順の例として，以下のように行えばよい．この手順で，要素が 1 個しかなかった 場合の処理も行える．
上記方針に従って deleteTop を実装せよ．以下のプログラムの main ルーチンは deleteTop を使用してテストするように変更されている．
/* 削除の関数を作成する．*/
#include <stdio.h>
#include <stdlib.h>
struct listNode {
int data;
struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
void insertTop(LISTNODE **, int);
int deleteTop(LISTNODE **);
void printList(LISTNODE *);
main()
{
LISTNODE *startPtr, *currentPtr;
int value;
startPtr = NULL;
printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
scanf("%d", &value);
while (value >= 0) {
insertTop(&startPtr, value);
printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
scanf("%d", &value);
}
printList(startPtr);
printf("top = %2d\n", deleteTop(&startPtr));
printList(startPtr);
return 0;
}
void insertTop(LISTNODE ** sPPtr, int data)
{
LISTNODE *currentPtr;
currentPtr = malloc(sizeof(LISTNODE));
if (currentPtr != NULL){
currentPtr->data = data;
currentPtr->nextPtr = *sPPtr;
*sPPtr = currentPtr;
}
}
int deleteTop(LISTNODE **sPPtr)
{
}
void printList(LISTNODE * cPtr)
{
while (cPtr != NULL) {
printf("%3d ", cPtr->data);
cPtr = cPtr->nextPtr;
}
putchar('\n');
}
list12x8.c
deleteTop は下の図 12.11 から 図12.14 の処理を行う関数として実装すればよい． deleteTop 呼び出し直後は仮引数 sPPtr へは startPtr へのポインタが渡されるため， 以下の状態になる．
図 12-11．deleteTop 呼び出し直後
これから消去される古い先頭要素の値が後で必要になるため，data フィールドと nextPtr フィールドをそれぞれ topValue, topNext へコピーする．
図 12-12．古い先頭要素のコピーした直後
消去する古い先頭要素領域を free 関数で解放する．
図 12-13．古い先頭の領域を free した直後
insertTop と同様に，リスト全体を表す変数として，常にリスト先頭要素へのポインタを main 関数の変数 startPtr に格納しておく必要がある． startPtr の内容を 2 番目の要素を指すように変更するか， 2番目がなければ NULL が格納されるようにする． これは引数の sPPtr と topNext を使えば可能である．
図 12-14．startPtr の値を変更し，削除が完了した後
最後に topValue の値を返り値として返せば deleteTop 関数は完成する．
次にリストが空であるかどうかの判定を行う関数 isEmpty を実装する． これはリスト全体を表す，リスト先頭要素へのポインタの値を変更しないので リスト先頭要素へのポインタを引数として実装できる．
以下のプログラムは isEmpty と deleteTop を使ってリストの要素を 全て出力するものである．isEmpty を実装せよ．
/* リストが空かどうかの判定 */
#include <stdio.h>
#include <stdlib.h>
struct listNode {
int data;
struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
void insertTop(LISTNODE **, int);
int deleteTop(LISTNODE **);
int isEmpty(LISTNODE *);
void printList(LISTNODE *);
main()
{
LISTNODE *startPtr, *currentPtr;
int value;
startPtr = NULL;
printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
scanf("%d", &value);
while (value >= 0) {
insertTop(&startPtr, value);
printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
scanf("%d", &value);
}
printList(startPtr);
while (!isEmpty(startPtr)){
printf("top = %2d is deleted\n", deleteTop(&startPtr));
printList(startPtr);
}
return 0;
}
void insertTop(LISTNODE ** sPPtr, int data)
{
LISTNODE *currentPtr;
currentPtr = malloc(sizeof(LISTNODE));
if (currentPtr != NULL){
currentPtr->data = data;
currentPtr->nextPtr = *sPPtr;
*sPPtr = currentPtr;
}
}
int deleteTop(LISTNODE **sPPtr)
{
int topValue;
LISTNODE *topNext;
topValue = (*sPPtr)->data;
topNext = (*sPPtr)->nextPtr;
free(*sPPtr);
*sPPtr = topNext;
return topValue;
}
int isEmpty(LISTNODE *sPtr)
{
}
void printList(LISTNODE * cPtr)
{
while (cPtr != NULL) {
printf("%3d ", cPtr->data);
cPtr = cPtr->nextPtr;
}
putchar('\n');
}
list12x9.c
以上のプログラムでスタックの実装は完成している． リスト 12.3 はここで説明 したものとほぼ同じ実装なので読んで理解せよ．スタックでは要素を先頭に挿入することを PUSH, 先頭から削除することを POP と呼ぶ．
キューがスタックと異なるのはデータを挿入できる位置が先頭ではなく，反対の末尾に 限られている点である．このため，最も古く挿入されたデータから先に削除される． FIFO (First-In, First-Out) と呼ばれる．
スタックと似た方法で実現できる．スタックと同様に 削除すべき要素の位置であるリスト先頭の要素へのポインタを記憶しておく他に， 挿入すべき要素の位置であるリスト末尾の要素へのポインタも記憶しておけばよい． リスト 12.5（修正版） を理解せよ．