前回の課題の演習が終わっていない人も多いので、 前半を講義で、後半は演習課題の続きとした。

配列のスタック

int stack[ 100 ] ;
int *sp = stack ;
void push( int x ) {
*sp = x ;
sp++ ;
}
int pop() {
sp-- ;
return *sp ;
}
void main() {
push( 1 ) ;
push( 2 ) ;
push( 3 ) ;
printf( "%d" , pop() ) ; // 3
printf( "%d" , pop() ) ; // 2
printf( "%d" , pop() ) ; // 1
}

この様なプログラムでは、最後に入れたデータを最初に取り出せるということで、 "Last In First Out(LIFO)"と呼ぶ。一般的にはスタック。

このようなスタックは、関数の戻り番地や局所変数管理に使われる。 また、上記のプログラムでは、stackの配列が100件分しかないので、 push()が連続100回呼び出されれば、配列をはみ出してしまう。

リストのスタック

前述のとおり、配列の大きさ以上のpush()できないので、 必要に応じてメモリを確保するリスト構造を使ってpush() , pop()を書いてみる。

struct List* sp = NULL ;
void push( int x ) {
// mallocに慣れてほしいので、わざと補助関数consを使わずに
struct List* n ;
n = (struct List*)malloc( sizeof( struct List ) ) ;
if ( n != NULL ) {
n->data = x ;
n->next = sp ;
sp = n ;
}
}
int pop() {
struct List* d = sp ;
int ans = sp->data ;
sp = sp->next ;
free( d ) ;
return ans ;
}