Thinkers'Studio
JavaとC言語の自習ツール
構造体配列を使ったスタックの例

 スタック は、「後入れ先出し」のデータ構造です(スタックのTipsで解説)。
 C言語プログラムでスタック構造を実現する例として、今回は固定サイズの構造体配列を使った簡易なものを紹介します。

スタックのデータ構造

 ここでは、次のような構造体配列にデータを入れます。
#define STACK_MAX 100
typedef struct {
    int idno;
    int data;
} stack_t;
stack_t stack[STACK_MAX]; //スタック用の構造体配列
 先頭のデータ位置は変数 spt に覚えます。
int spt = -1;             //スタックポインタ(空のときは-1)
 これをスタック用配列の最後に保存したエントリを指す添字として使います。 スタックが空の状態では、添字の先頭 0 より小さい -1 とします。
 このような、スタックの現在位置を指し示すデータを一般にスタックポインタと呼びます。
 これらのデータは push と pop の両関数から使います。引数で受け渡しせずに、グローバルな変数として使うことにしましょう。

データを入れる操作(push関数)

 引数で指定されたデータをスタックの先頭、つまり "stack[spt]" に入れます。
// ---- データをスタックに入れる ----
int push( int no, int dt ) {
    if( spt >= STACK_MAX-1 ) return -1;

    spt++;
    stack[spt].idno = no;
    stack[spt].data = dt;
    return 0;
}
 配列のサイズを超えて書き込まないよう先頭でチェックします。"スタックオーバーフロー" になるなら -1 を返しています。
 スタックポインタをインクリメントしてから、配列要素に代入します。

データを取り出す操作(pop関数)

 スタックポインタが指す先頭のデータを取り出して、引数に返します。
// ---- スタックからデータを取り出す ----
int pop( int *no, int *dt ) {
    if( spt < 0 ) return -1;

    *no = stack[spt].idno;
    *dt = stack[spt].data;
    spt--;
    return 0;
}
 値を取り出したら、スタックポインタをデクリメントします。 データの取り出しといっても、実際にはデータを参照してスタックポインタをずらすだけです。配列要素もクリアしません。次の push で上書きされます。
 pop でも関数の先頭で、添字 0 より前を参照しに行かないように "スタックアンダーフロー" のチェックを行います。

main関数の例

 ここまでの内容を使ったプログラムの main の例です。
 スタックの Tips で紹介した(平成22年秋期 基本情報技術者試験 午前問5)で正解とされるデータ列をこのスタックを使って実際に取り出します。
main()
{
    int n, c;

    push( 10, 'A' );
    push( 20, 'B' );
    push( 30, 'C' );
    if( pop( &n, &c ) == 0 ) printf( "%d, %c\n", n, c );
    if( pop( &n, &c ) == 0 ) printf( "%d, %c\n", n, c );
    push( 40, 'D' );
    if( pop( &n, &c ) == 0 ) printf( "%d, %c\n", n, c );
    if( pop( &n, &c ) == 0 ) printf( "%d, %c\n", n, c );
}

(今回のクイズはありません)

[ 関連記事 ] スタック

前回のクイズの答え: cm または m のデータを cm単位に統一して保存するには? (前回の問題を見る
 strtod では変換不能な文字列が返るので、それを利用します。
main()
{
    char hstr[][24] = { "172.3cm", "1.56m", "184.5cm", "1.675m" }, *ep;
    double d, cmh[4]; //cm単位の身長データ配列 
    int i;

    for( i = 0; i < 4; i++ ) {
        d = strtod( hstr[i], &ep ); //double型に変換不能な部分がepに入る
        //単位がmなら、dに100を掛けてcm単位へ。そうでなければdのまま
        if( *ep != '\0' ) cmh[i] = (ep[0]=='m') ? d*100 : d;
    }
}