前回の課題の演習が終わっていない人も多いので、 前半を講義で、後半は演習課題の続きとした。
配列のスタック
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 ; }