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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

//配列スタックの実装
#include<stdio.h>
 
#define MaxSize 50
 
typedef struct Stack_Array{
    int data[MaxSize];
    int top;
}Sqstack,*pSqstack;
 
void Initstack();  //初期化
int Isempty();     //スタックが空かチェック
int Push();        //プッシュ（スタックに要素を追加）
int Pop();         //ポップ（スタックから要素を取り出す）
int Gettop();      //スタックのトップ要素を取得
 
int main(void)     //テスト
{
    int val;
    Sqstack s1;
    pSqstack ps1=&s1;
    Initstack(&s1);  //初期化
 
    if(Isempty(&s1))  //スタックが空かチェック
        printf("スタックは空だよ！\n");
    else printf("スタックは空じゃないよ！\n");
 
    printf("プッシュする要素の値を入力してね");    //プッシュ 1
    scanf("%d",&val);
    Push (ps1,&val);
 
    printf("プッシュする要素の値を入力してね");    //プッシュ 2
    scanf("%d",&val);
    Push (ps1,&val);
 
    if(Isempty(ps1))        //スタックが空かチェック
        printf("スタックは空だよ！\n");
    else printf("スタックは空じゃないよ！\n");
 
    if(Gettop(ps1,&val))    //スタックのトップ要素を取得
        printf("スタックのトップは%dだよ\n",val);
    else printf("スタックのトップ要素を見つけられなかったよ！\n");
 
    if(Pop(ps1,&val))    //ポップ
        printf("ポップ成功！取り出した要素は%dだよ\n",val);
    else printf("ポップ失敗！\n");
 
    return 0;
}
//初期化
void Initstack (pSqstack ps1)
{
    ps1->top=-1;
    return;
    
//    スタックが空か判断
int    Isempty(pSqstack ps1)
    
    if(ps1->top==-1)
        return 1;
    else return 0;
    
//    スタックが満杯じゃなければプッシュするよ
int    Push(pSqstack ps1,int *val)//*val:アドレスを受け取る (int *(&val    )
    
    if(ps1->top==MaxSize)
        return 0;
    else
    {
        ps1->top++;
        ps1->data[ps1->top]=*val;//ここで渡されるのは値。ここの*valは*(&val)で、&valはメイン関数から入力される
                //ps1->data[++ps1->top]=*val; とも書ける。必ず++ps1->top
        return 1;
    }
}
//スタックが空じゃなければポップして、valでトップ要素を返すよ
int Pop(pSqstack ps1,int *val)
{
    if(Isempty(ps1))
        return 0;
    else
    {
        *val=ps1->data[ps1->top--];
        return 1;
    }
}
//スタックのトップ要素を取得して、valで返すよ
int Gettop(pSqstack ps1,int *val)
{
    if(Isempty(ps1))
        return 0;
    else 
    {
        *val=ps1->data[ps1->top];
        return 1;
    }
}

  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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

//スタックの連結リスト実装
#include <stdio.h>
#include <stdlib.h>

#define Stack_Init_Size 10 // 初期化スタックの最大長
#define StackIncrement 10 // スタックの最大スペースが足りない場合に増やす長さ
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *base; // スタックのベースポインタ
    ElemType *top; // スタックのトップポインタ
    int stack_size; // スタックの最大長
} SqStack;

// スタックの初期化
Status InitStack(SqStack *S) {
    // 初期スペースを割り当てるよ
    S->base = (ElemType *) malloc(Stack_Init_Size * sizeof(ElemType));
    if (!S->base) {
        exit(0);
    }
    S->top = S->base; /// トップとベースのポインタは同じだよ
    S->stack_size = Stack_Init_Size; // スタックの最大長は初期長と同じ
    return 1;
}

// スタックが空かどうかを判断するよ。スタックのトップとベースのポインタが同じなら空だね。
Status EmptyStack(SqStack *S) {
    return S->base == S->top;
}

// スタックの実際の長さを取得するよ。トップポインタからベースポインタを引くと長さがわかる。
Status LengthStack(SqStack *S) {
    if (S->top == S->base) {
        return 0;
    }
    return (Status) (S->top - S->base);
}

// スタックのトップにある要素を取得するよ。引数eにトップの要素を入れる。
Status GetTopStack(SqStack *S, ElemType *e) {
    if (S->top == S->base) {
        return 0;
    } 
    *e = *(S->top - 1);
    return 1;
}

// プッシュ（スタックに要素を追加）。引数eは追加する要素。
Status PushStack(SqStack *S, ElemType e) {
    // スタックの最大長が足りなくなったら、新しい領域を確保して長さを増やすよ。
    if (S->top - S->base >= S->stack_size) {
        S->base = (ElemType *)realloc(S->base, (S->stack_size + StackIncrement) * sizeof(ElemType));
        if (!S->base) {
            return 0;
        }
        // スタックのトップポインタは、ベースポインタに以前のスタック最大長を足したものになる。
        S->top = S->base + S->stack_size;
        // スタックの現在の最大長は、以前の最大長と増やした長さの合計になる。
        S->stack_size += StackIncrement;
    }
    *S->top++ = e; // まず値を代入して、その後にトップポインタを上にずらす。
    return 1;
}

// ポップ（スタックから要素を取り出す）。引数eに取り出した要素を入れる。
Status PopStack(SqStack *S, ElemType *e) {
    if (S->base == S->top) {
        return 0;
    }
    *e = *--S->top; // まずトップポインタを下にずらして、その後に値を代入する。
    return 1;
}

// スタックを破棄するよ。領域を解放して、トップとベースのポインタをNULLにして、長さを0にする。
Status DestroyStack(SqStack *S) {
    free(S->base);
    S->base = S->top = NULL;
    S->stack_size = 0;
    return 1;
}

// スタックを巡回して、各要素を順番に表示するよ。
Status StackTraverse(SqStack *S) {
    ElemType *p;

    if (S->top == S->base) {
        printf("スタックはNULLだよ。\n");
        return 0;
    }
    p = S->top;
    // スタックのトップから順番に下へ巡回する。
    while (p > S->base) {
        p--;
        printf("%d ", *p);
    }
    printf("\n");
    return 1;
}

int main() {
    SqStack q, *S;
    S = &q;

    int i, n, e;

    printf("NULLスタックを作成するよ:\n");
    InitStack(S);

    printf("スタックの長さを入力してね:\n");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d", &e);
        PushStack(S, e);
    }
    printf("スタックはNULLかな？\n");

    if (EmptyStack(S)) {
        printf("うん！\n");
    } else {
        printf("ううん！\n");
    }
    printf("スタックの長さは %d だよ。\n", LengthStack(S));

    printf("スタックの中身はこれ:\n");
    StackTraverse(S);

    GetTopStack(S, &e); // eにトップの値を格納
    printf("トップのデータは %d だよ。\n", e);

    printf("スタックに入れるデータを入力してね:\n");
    scanf("%d", &e);
    PushStack(S, e);
    printf("新しいスタックはこれ:\n");
    StackTraverse(S);

    printf("トップのデータを削除するよ: ");
    PopStack(S, &e); // eに削除した値を格納
    printf("%d\n", e);

    printf("新しいスタックはこれ:\n");
    StackTraverse(S);

    printf("スタックを破棄するよ:\n");
    DestroyStack(S);
    StackTraverse(S);

    return 0;
}