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();      //get 堆疊頂元素
 
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))    //get 堆疊頂元素
        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;
	}
}
//get棧頂元素，用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("Stack is 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("Creat a NULL Stack :\n");
    InitStack(S);

    printf("input the length of the Stack :\n");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d", &e);
        PushStack(S, e);
    }
    printf("Is the stack NULL?\n");

    if (EmptyStack(S)) {
        printf("Yes!\n");
    } else {
        printf("No!\n");
    }
    printf("The length of stack is %d.\n", LengthStack(S));

    printf("The stack is :\n");
    StackTraverse(S);

    e = GetTopStack(S, &e);
    printf("The top data is %d.\n", e);

    printf("input the data to the stack :\n");
    scanf("%d", &e);
    PushStack(S, e);
    printf("The new stack is :\n");
    StackTraverse(S);

    printf("Delete the top data : ");
    e = PopStack(S, &e);
    printf("%d\n", e);

    printf("The new stack is :\n");
    StackTraverse(S);

    printf("Destroy the stack :\n");
    DestroyStack(S);
    StackTraverse(S);

    return 0;
}