ももの知恵の樹

C言語アルゴリズム-スタック

スタック (stack)データ構造について

スタックとは、データを上に積み上げていき、最後に入力したデータが先に出力されるという特徴をもつデータ構造です。スタックにデータを挿入することを「push（積む）」といい、新しいデータが一番上に追加されます。スタックからデータを出すことを「pop（降ろす、取り出す）」といい、一番上にある新しいデータが優先して取得されます。このような「最後に入った物が最初に出てくる」というデータの入出力方式は「Last In, First Out (LIFO)」あるいは「First In, Last Out (FIFO)」と呼ばれます。


スタックの動作例


(push 1)  stack : [ 1 ]
(push 2)  stack : [ 1 2 ]
(pop)     stack : [ 1 ]     -> data : 2
(push 3)  stack : [ 1 3 ]
(push 4)  stack : [ 1 3 4 ]
(pop)     stack : [ 1 3 ]   -> data : 4
(pop)     stack : [ 1 ]     -> data : 3
(pop)     stack : [ ]       -> data : 1

C言語によるスタック実現プログラム


#include <stdio.h>

#define STACK_SIZE 10  /* スタックデータ数の最大値 */

/* スタックデータの定義 */
struct stack{
    int num;              /* スタックに存在する要素数 */
    int data[STACK_SIZE]; /* 要素の格納先 */
};
typedef struct stack stack_t;

/*!
 * @brief         スタックにデータを挿入する
 * @param[in/out] stk        スタック
 * @param[in]     push_data  挿入するデータ
 * @return        0          success
 * @return        -1         failure
 */
int
stack_push(stack_t *stk, int push_data)
{
    /* スタックが満杯になっていないかチェックする */
    if(stk->num >= STACK_SIZE) return(-1);

    stk->data[stk->num] = push_data;
    stk->num++;
    return(0);
}

/*!
 * @brief         スタックからデータを取得する
 * @param[in/out] stk        スタック
 * @param[out]    pop_data   挿入するデータ
 * @return        0          success
 * @return        -1         failure
 */
int
stack_pop(stack_t *stk, int *pop_data)
{
    /* スタックが空でないかチェックする */
    if(stk->num < 1) return(-1);

    stk->num--;
    *pop_data = stk->data[stk->num];
    return(0);
}

/*!
 * @brief     スタック内にある要素を一覧表示する
 * @param[in] stk        スタック
 */
static void
stack_print(stack_t *stk)
{
    int i;
        
    printf("stack : [ ");
    for(i = 0; i < stk->num; i++){
        printf("%d ", stk->data[i]);
    }
    printf("]\n");
}

/*!
 * @brief  初期化処理
 */
static void
stack_init(stack_t *stk)
{
    /* スタックの要素数を初期化 */
    stk->num = 0;
}

int
main(void)
{
    stack_t stk = {0};
    int data = 1;

    /* スタックを初期化する */
    stack_init(&stk);

    /* スタックを満たすまで数値をpushする */
    while(stack_push(&stk, data) == 0){
        printf("(push %2d) ", data);
        stack_print(&stk);
        data++;
    }

    /* スタック内要素を全てpopする */
    while(stack_pop(&stk, &data) == 0){
        printf("(pop  %2d) ", data);
        stack_print(&stk);
    }

    return(0);
}

関連ページ