「栈-顺序结构」C语言实现

顺序栈示意图

待补充。。。

数据结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
/*------------------- 顺序栈结构定义 ----------------------*/

#define MAXSIZE 100

typedef int ElemType;

// 顺序栈的类型定义
typedef struct {
    ElemType * pBase;  // 数组基地址
    int top;   // 栈顶指针，起初为 -1
} SqStack, *pSqStack;

/*------------------- 顺序栈结构定义 ----------------------*/

源码

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
/*
 * 功能: 栈-顺序结构
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/A1-LatestVersion
 * Date: 2022-09-14
 */

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


/*------------------- 顺序栈结构定义 ----------------------*/

#define MAXSIZE 100

typedef int ElemType;

// 顺序栈的类型定义
typedef struct {
    ElemType * pBase;  // 数组基地址
    int top;   // 栈顶指针，起初为 -1
} SqStack, *pSqStack;

/*------------------- 顺序栈结构定义 ----------------------*/


// 函数前置定义
void InitStack(pSqStack S);
bool IsFull(pSqStack S);
bool PushStack(pSqStack S, ElemType elem);
void TraverseStack(pSqStack S);
bool IsEmpty(pSqStack S);
bool PopStack(pSqStack S, ElemType * pElem);
void ClearStack(pSqStack S);
void DestoryStack(pSqStack S);


// 主函数
int main(void)
{ 
    SqStack S;

    InitStack(&S);
    PushStack(&S, 1);
    PushStack(&S, 2);
    PushStack(&S, 3);
    PushStack(&S, 4);
    PushStack(&S, 5);
    TraverseStack(&S);

    ElemType e;
    PopStack(&S, &e);
    PopStack(&S, &e);
    PopStack(&S, &e);
    TraverseStack(&S);

    DestoryStack(&S);
    TraverseStack(&S);

    return 0;
}

// 初始化
void InitStack(pSqStack S)
{
    // 分配顺序存储空间
    S->pBase = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);

    S->top = -1; 
}

bool IsFull(pSqStack S)
{
    return (S->top+1 == MAXSIZE );
}

// 压栈
bool PushStack(pSqStack S, ElemType elem)
{
    if ( IsFull(S) ) {
        printf("栈已满，压栈失败！");
        return false;
    }

    S->pBase[++S->top] = elem;  // 入栈用前缀 ++

    return true;
}

// 遍历栈
void TraverseStack(pSqStack S)
{
    for ( int i = 0; i < S->top+1; i++ ) {
        printf("%d ", S->pBase[i]);
    }

    printf("\n");
}

bool IsEmpty(pSqStack S)
{
    return ( -1 == S->top );
}

// 出栈
bool PopStack(pSqStack S, ElemType * pElem)
{
    if ( IsEmpty(S) ) {
        printf("栈为空，出栈失败！");
        return false;
    }

    *pElem = S->pBase[S->top--];  // 出栈用后缀 --
}

// 清空栈
void ClearStack(pSqStack S)
{
    S->top = -1;
}

// 销毁栈
// 释放动态内存
void DestoryStack(pSqStack S)
{
    free(S->pBase);
    S->pBase = NULL;

    S->top = -1;
}