C言語関数辞典

≫ ホーム ≫ C言語Tips集 ≫ 配列・メモリ領域 ≫ 配列を簡易的なスタックとして使用する

C言語Tips集 - 配列を簡易的なスタックとして使用する

C言語でスタック (stack) を実装するにはさまざまな方法がありますが，ここではあくまで配列を簡易的なスタックとして扱えるようにすることを目的とします．

スタックには PUSH 操作と POP 操作の 2 種類の動作が存在します．これらの動作を行う関数を作成すれば配列を簡易的なスタックとして使用することができます．

PUSH 操作の実装

PUSH 操作は以下の 2 つの手順が必要になります．

スタックにデータを積む
スタックポインタをインクリメントする

図1 PUSH操作のイメージ図

また，実用上，配列の最大要素数を超えるデータが PUSH されたときのことを考えて，場合わけをする必要があります．以下に PUSH 操作を行う関数の実装例を示します．

/**
 * 配列にプッシュする
 * @param[in,out] stack 配列
 * @param[in] data 配列にプッシュする値
 * @param[in,out] sp スタックポインタ
 * @param[in] n 配列の最大要素数
 * @retval >=1 配列に格納されている要素の数
 * @retval 0 配列にプッシュに失敗
 */
int ArrayPush(int *stack, int data, int *sp, size_t n) {
    if ( *sp < n ) {
        stack[(*sp)++] = data;
        return *sp;
    } else { /* 配列の要素数を超えるデータが PUSH されたとき */
        return 0;
    }
}

スタックポインタ sp は次の値を格納する位置情報を保持しておく必要があるため，引数として受け取り，ポインタ渡しで返すようにしています．

POP 操作の実装

POP 操作は以下の 2 つの手順が必要になります．

スタックポインタをデクリメントする
スタックからデータを取り出す

図2 POP操作のイメージ図

実際にはデータを取り出す (スタック上からデータを消去する) わけではなく，スタックポインタをずらすことによって PUSH 操作が行われたときに上書き可能にするのがポイントです．以下に POP 操作を行う関数の実装例を示します．

/**
 * 配列からポップする
 * @param[in] stack 配列
 * @param[in,out] sp スタックポインタ
 * @return ポップした値
 */
int ArrayPop(int *stack, int *sp) {
    if ( *sp > 0 ) {
        return stack[--(*sp)];
    } else {
        return 0;
    }
}

C言語サンプルプログラム

上記で例に挙げた関数を使用して，配列を簡易的なスタックとして使用する例を以下に示します．

/* header files */
#include <stdio.h>
#include <stdlib.h>

/* macros */
#define N 8

/* functions */
int ArrayPush(int *stack, int data, int *sp, size_t n);
int ArrayPop(int *stack, int *sp);

/* main */
int main(void) {
    int data;
    int stack[N]; /* 配列 (スタック) */
    int sp = 0; /* スタックポインタ */

    /* 配列にプッシュする */
    ArrayPush(stack, 10, &sp, N);
    printf("Push: %d\n", 10);

    ArrayPush(stack, 20, &sp, N);
    printf("Push: %d\n", 20);

    ArrayPush(stack, 30, &sp, N);
    printf("Push: %d\n", 30);

    ArrayPush(stack, 40, &sp, N);
    printf("Push: %d\n", 40);

    /* 配列からポップする */
    while ( sp ) {
        data = ArrayPop(stack, &sp);
        printf("Pop: %d\n", data);
    }

    return EXIT_SUCCESS;
}

/**
 * 配列にプッシュする
 * @param[in,out] stack 配列
 * @param[in] data 配列にプッシュする値
 * @param[in,out] sp スタックポインタ
 * @param[in] n 配列の最大要素数
 * @retval >=1 配列に格納されている要素の数
 * @retval 0 配列にプッシュに失敗
 */
int ArrayPush(int *stack, int data, int *sp, size_t n) {
    if ( *sp < n ) {
        stack[(*sp)++] = data;
        return *sp;
    } else {
        return 0;
    }
}
/**
 * 配列からポップする
 * @param[in] stack 配列
 * @param[in,out] sp スタックポインタ
 * @return ポップした値
 */
int ArrayPop(int *stack, int *sp) {
    if ( *sp > 0 ) {
        return stack[--(*sp)];
    } else {
        return 0;
    }
}

実行例

サンプルプログラムの実行結果は以下のようになります．

Push: 10
Push: 20
Push: 30
Push: 40
Pop: 40
Pop: 30
Pop: 20
Pop: 10

Cプログラマの必読書

たくさんあるC言語関連の書籍の中でも特に役に立った本です．よかったら参考にしてみてください．

C実践プログラミング第3版

C言語の実践的参考書．少々値段は張りますが初心者を脱しようとしている人は絶対に読むべきです．
文法だけでなく，コーディングスタイルやデバッグなど文字通り「実践的」なことが書かれているので非常にためになります．オライリーの本は，読みにくい本が多いのですが本書はとても読みやすくオススメです．

C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

ポインタの解説書としては最高の書籍です．
この1冊でポインタを完全に理解することができます．全くの初学者が読むには敷居が高いですが，入門書を読み終えた後に読むと非常に有益です．

データ構造

配列を簡易的なキューとして使用する

スポンサー