栈基础函数C语言实现

Share 
本demo的变量设为elemType，若有改变变量类型的需求，到h文件中的typedef中改变即可

Talk is cheap;

Show you the code;

栈基础函数.h

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
//
//  API.h
//  栈、队列的实现
//
//  Created by SaberDa on 16/9/25.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#ifndef API_h
#define API_h

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

#define STACK_INIT_SIZE 100
#define STACK_INCREAT_SIZE 1
#define ERROR 0
#define OK 1

typedef char elemType;

//顺序栈的实现
typedef struct {
    
    elemType *base;
    elemType *top;       //非空时top指针永远指向栈顶元素的下一个位置
    int stacksize;
    
}SqStack;

//栈链的实现
typedef struct node{
    
    int data;
    struct node *next;
    
}stackNode, *linkStack;

//初始化顺序栈
int initSqStack(SqStack *S);

//销毁顺序栈
int destorySqStack(SqStack *S);

//求顺序栈的长度
int lengthOfSqStack(SqStack *S);

//判断顺序栈是否为空
int emptyOfSqStack(SqStack *S);

//判断顺序栈是否为满
int fullOfSqStack(SqStack *S);

//清空顺序栈
void cleanSqStack(SqStack *S);

//获取栈顶元素
elemType getTop(SqStack *S);

//遍历顺序栈
int printSqStack(SqStack *S, int n);

//顺序栈入栈
int pushSqStack(SqStack *S, elemType e);

//顺序栈出栈
elemType popSqStack(SqStack *S);

//在顺序栈查找元素
//此函数会改变栈元素的地址，所以最后调用
elemType getElemInSqStack(SqStack *S, int i);

#endif /* API_h */

栈基础函数.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
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
//
//  API.c
//  栈、队列的实现
//
//  Created by SaberDa on 16/9/25.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#include "API.h"


int initSqStack(SqStack *S) {
    
    S -> base = (elemType *)malloc(STACK_INIT_SIZE * sizeof(elemType));
    if (!S -> base) {
        return ERROR;
    }
    S -> top = S -> base;
    S -> stacksize = STACK_INIT_SIZE;
    return 0;
    
}

int destorySqStack(SqStack *S) {
    
    if (S -> base) {
        free(S -> base);
        S -> base = NULL;
        S -> top = NULL;
        S -> stacksize = 0;
    }
    return 0;
    
}

int lengthOfSqStack(SqStack *S) {
    
    return (int)(S -> top - S -> base)+1;
    
}

int emptyOfSqStack(SqStack *S) {
    
    if (S -> top == S -> base) {
        return OK;
    }else
        return ERROR;
    
    //return S -> top == S -> base ? OK : ERROR;

}

int fullOfSqStack(SqStack *S) {
    
    return (S -> top - S -> base) >= S -> stacksize ? OK : ERROR;
    
}

void cleanSqStack(SqStack *S) {
    
    if (!emptyOfSqStack(S)) {
        S -> top = S -> base;
    }
    
}

elemType getTop(SqStack *S) {
    
    elemType e;
    if (!emptyOfSqStack(S)) {
        return ERROR;
    }
    S -> top --;
    e = *S -> top;
    
    return e;
}

int printSqStack(SqStack *S, int n) {
    
    if (!emptyOfSqStack(S)) {
        printf("ERROR\n");
        return ERROR;
    }
    S -> top = S -> base;
    for (int i = 0; i < n; i++) {
        printf("%c\t", *(S -> top)++);
    }
    return 0;
}

int pushSqStack(SqStack *S, elemType e) {
    
    if (S -> top - S -> base >= S -> stacksize) {
        (*S).base = (elemType *)realloc((*S).base, ((*S).stacksize + STACK_INCREAT_SIZE) * sizeof(elemType));
        if (!S -> base) {
            return ERROR;
        }
        S -> top = S -> base + S -> stacksize;
        S -> stacksize += STACK_INCREAT_SIZE;
    }
    *(S -> top)++ = e;
    S -> stacksize++;
    return 0;
}

elemType popSqStack(SqStack *S) {
    
    elemType e;
    if (S -> top == S -> base) {
        printf("ERROR");
        return ERROR;
    }
    e = *--S -> top;
    //S -> stacksize--;
    return e;
    
}

elemType getElemInSqStack(SqStack *S, int i) {
    
    elemType e = 0;
    SqStack *L = S;
    for (int j = 0; j < (i-1); j++) {
        (L -> base)++;
    }
    e = *(L -> base);
    return e;
}

main.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
#include "栈基础函数.h"

int main(int argc, const char * argv[]) {
    
    SqStack stack;
    initSqStack(&stack);
    
    //入栈demo
    pushSqStack(&stack, 8);
    pushSqStack(&stack, 9);
    pushSqStack(&stack, 90);
    pushSqStack(&stack, 99);
    pushSqStack(&stack, 18);
    pushSqStack(&stack, 82);
    pushSqStack(&stack, 83);
    pushSqStack(&stack, 84);
    pushSqStack(&stack, 85);
    pushSqStack(&stack, 86);
    pushSqStack(&stack, 88);

    
    printf("%d\n", getTop(&stack));
    
    printf("%d\n", lengthOfSqStack(&stack));
    
    printSqStack(&stack, lengthOfSqStack(&stack));
    
    return 0;
}