C言語-スタック

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

1 スタック

　スタックとは、後入れ先出し記憶領域のことである。スタックにデータを保存したり、取り出したりする様子は、ちょうど本を積み重ねているのに似ている。
Stack 　保存する本（データ）は上へ上へと積んでいき、取り出すときは、上から順に取り出す。積んである本（データ）を途中から取ることはできない。
　データをスタックに保存することをプッシュ(push)、スタックからデータを取り出すことをポップ(pop)するという。

スタックの処理をする関数を作成する。スタックするデータは1つの整数値とする。[pushpop1.c]

 1:
 2:
 3:
 4:
 5:
 6:
 7:
 8:
 9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:

#include <stdio.h>
#include <stdlib.h>

#define STACK_MAX  20               /* スタックサイズ */
#define STACK_OK   0x8000           /* スタック成功を表すデータ */
#define STACK_FULL STACK_OK + 1     /* スタックサイズを超えたときのデータ */
#define STACK_END  STACK_OK + 2     /* スタックの終わりを表すデータ */
/* 関数のプロトタイプ宣言 */
int     push(int);          /* スタックにデータを積む関数 */
int     pop(void);          /* スタックからデータを取り出す関数 */
void    print_stack(void);  /* スタックの内容をすべて表示する関数 */
/* グローバル変数 */
int     stack[STACK_MAX];   /* スタック領域 [0] - [19] */
int     stack_pointer = 0;  /* スタックポインタ */

void main(void)
{
    int     data[10] = { 1,2,3,4,5,6,7,8,9,10 };
    int     x, n;
    char    buff[80];

    for(x = 0; x < 10; ++x){
        printf("%d整数をスタックに積む\n", data[x]);
        push(data[x]);      /* データをスタックに積む */
        print_stack();
        printf("Hit RETURN key ");
        gets(buff);
    }
    while(1){
        n = pop();          /* スタックから取り出し */
        if(n == STACK_END){
            printf("スタックデータ終了 \n");
            break;
        }
        printf("%d ", n);
    }
    printf("\n");
}
int push(int d)
{
    if(stack_pointer >= STACK_MAX)  /* スタックポインタが最大 */
        return(STACK_FULL);         /* STACK_FULLを返す */
    stack[stack_pointer] = d;       /* スタックにデータ格納 */
    ++stack_pointer;                /* スタックポインタに1加算 */
    return(STACK_OK);               /* STACK_OKを返す */
}
int pop(void)
{
    if(stack_pointer == 0)          /* スタックポインタが0 */
        return(STACK_END);          /* STACK_ENDを返す */
    --stack_pointer;                /* スタックポインタから1減算 */
    return(stack[stack_pointer]);   /* スタックのデータを返す */
}
void print_stack(void)
{
    int     i;

    for(i = stack_pointer - 1; i >= 0; --i)
        printf("%4d", stack[i]);
    printf("\n");
}

実行結果
1整数をスタックに積む 1 Hit RETURN key 2整数をスタックに積む 2 1 Hit RETURN key 3整数をスタックに積む 3 2 1 Hit RETURN key 4整数をスタックに積む 4 3 2 1 Hit RETURN key 5整数をスタックに積む 5 4 3 2 1 Hit RETURN key 6整数をスタックに積む 6 5 4 3 2 1 Hit RETURN key 7整数をスタックに積む 7 6 5 4 3 2 1 Hit RETURN key 8整数をスタックに積む 8 7 6 5 4 3 2 1 Hit RETURN key 9整数をスタックに積む 9 8 7 6 5 4 3 2 1 Hit RETURN key 10整数をスタックに積む 10 9 8 7 6 5 4 3 2 1 Hit RETURN key 10 9 8 7 6 5 4 3 2 1 スタックデータ終了

実行結果

  1整数をスタックに積む
     1
  Hit RETURN key
  2整数をスタックに積む
     2   1
  Hit RETURN key
  3整数をスタックに積む
     3   2   1
  Hit RETURN key
  4整数をスタックに積む
     4   3   2   1
  Hit RETURN key
  5整数をスタックに積む
     5   4   3   2   1
  Hit RETURN key
  6整数をスタックに積む
     6   5   4   3   2   1
  Hit RETURN key
  7整数をスタックに積む
     7   6   5   4   3   2   1
  Hit RETURN key
  8整数をスタックに積む
     8   7   6   5   4   3   2   1
  Hit RETURN key
  9整数をスタックに積む
     9   8   7   6   5   4   3   2   1
  Hit RETURN key
  10整数をスタックに積む
    10   9   8   7   6   5   4   3   2   1
  Hit RETURN key
  10 9 8 7 6 5 4 3 2 1 スタックデータ終了

　10個のデータを24行目の関数pushで、スタックに格納していく。
　途中の状態を表示するために25行目でスタックの内容をすべて表示し、26,27行目で入力待ちにし、実行を停止している。

　スタックに格納されたデータを30行目の関数popで取りだし、35行目で表示している。取り出すデータが無くなったら、関数popは STACK_END(0x8002)を返すので31行目で終わりかどうかを判定している。

　グローバル変数stack_pointerでスタックを管理しているので、41行目でスタック領域を越えていないか判定している。越えていたら41行目でSTACK_FULLを返す。

　43行目で配列stackのstack_pointer番にデータを格納し、44行目でstack_pointerに1加算しておく。

　49行目でスタック領域が空かどうかをグローバル変数stack_pointerで判定し、空なら50行目でSTACK_ENDを返す。
　51行目でstack_pointerから1減じてから、52行目で配列stackのstack_pointer番のデータを返す。

　実行結果の表示では、スタックのデータが横向きに表示されるが、左端を上と考えれば、スタックに積まれたデータが上へ上へと積まれていく様子がわかる。

                    3
    3   2   1  →   2
                    1

　最後に、スタックからすべてのデータを取りだして表示している。スタックの一番上のデータから順に取り出され、入力した順と逆に並んでいるのがわかる。