栈是一种经常使用的数据结构，软硬件学习过程中都有它的身影，是一种必须掌握的数据结构，本文将结合代码简单两种栈的实行方式。

栈的定义

栈(Stack)是限定仅在表尾进行插入与删除操作的线性表。于是栈也有两种实现方式，顺序栈和链栈。

代码实现

顺序栈(SqStack)

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
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//顺序栈定义
typedef struct
{
    SElemType *top; //栈顶指针
    SElemType *base; //在栈构造之前和销毁之后为NULL
    int stacksize; //当前已分配大小
}SqStack;

//初始化
Status InitStack(SqStack *S)
{
    S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if (!S->base) return ERROR;
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

//判空
Status StackEmpty(SqStack *S)
{
    if (S->top == S->base)
        return OK;
    return ERROR;
}

//栈满
Status StackFull(SqStack *S)
{
    if (S->top - S->base >= S->stacksize)
        return OK;
    return ERROR;
}

//栈顶
Status GetTop(SqStack *S, SElemType* e)
{
    if (StackEmpty(S))
        return ERROR;
    (*e) = *(S->top - 1);
    return OK;
}

//压栈
Status PushStack(SqStack *S, SElemType e)
{
    if (StackFull(S))
    {
        S->base = (SElemType *)realloc(S->base,
            (S->stacksize + STACKINCREMENT)*sizeof(SElemType));
        if (!S->base) return ERROR;
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
    return OK;
}

//弹栈
Status PopStack(SqStack *S, SElemType* e)
{
    if (StackEmpty(S)) return ERROR;
    (*e) = *(--S->top);
    return OK;
}

//清空
Status ClearStack(SqStack *S)
{
    S->top = S->base;
    S->stacksize = 0;
    return OK;
}

//销毁
Status DestroyStack(SqStack *S)
{
    free(S->base);
    S->top = NULL;
    S->base = NULL;
    S->stacksize = 0;
    return OK;
}

//长度
int Length(SqStack *S)
{
    return S->top - S->base;
}

//遍历栈
Status Traverse(SqStack *S)
{
    SElemType *p;
    p = S->top - 1;
    while (p >= S->base)
    {
        printf("%d ", *p);
        p--;
    }
    printf("\n");
    return OK;
}

完整代码可参见：GitHub

链栈(LinkStack)

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
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//栈节点定义
typedef struct SNode
{
    SElemType data;
    struct SNode *next;
}SNode, *LinkStack;

//初始化
Status InitStack(LinkStack *S)
{
    *S = (SNode *)malloc(sizeof(SNode));
    if (!(*S)) return ERROR;
    (*S)->next = NULL;
    return OK;
}

//栈空
Status StackEmpty(LinkStack S)
{
    if (!S->next)
        return OK;
    return ERROR;
}

//压栈
Status PushStack(LinkStack S, SElemType e)
{
    SNode *p;
    p = (SNode *)malloc(sizeof(SNode));
    if (!p) return ERROR;
    p->data = e;
    p->next = S->next;
    S->next = p;
    return OK;
}

//弹栈
Status PopStack(LinkStack S, SElemType *e)
{
    SNode *p;
    if (StackEmpty(S))
        return ERROR;
    p = S->next;
    S->next = p->next;
    (*e) = p->data;
    free(p);
    return OK;
}

//遍历栈
Status Traverse(LinkStack S)
{
    SNode *p;
    p = S->next;
    while (p)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

完整代码可参见：GitHub

DONE！
所示代码如有错误请多加指正，谢谢