栈的基本操作及其应用_栈的基本操作代码

---

一、栈的基本概念

栈（stack）是限定仅在表尾进行插入和删除操作的线性表
1

我们把允许插入和删除的一端成为栈顶，另一端为栈底，不含任何数据元素的栈称为空栈。特点是“先进后出（LIFO结构）”

二、栈的基本操作

1.创建一个栈

代码如下（示例）：

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

#define StackInitSize 10 // 初始化栈的最大长度
#define StackIncrement 10 // 若栈最大空间不够时，需要增加的长度
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType* base; // 栈底指针
    ElemType* top; // 栈顶指针
    int stacksize; // 栈的最大长度
} SqStack;
1
2
3
4
5
6
7
8
9
10
11
12
13

2.初始化栈

代码如下（示例）：

//构造一个空栈S
Status InitStack(SqStack &S) {
    // 分配初始空间
    S->base = (ElemType*)malloc(StackInitSize * sizeof(ElemType));
    if (!S->base) {
        exit(0);
    }
    S->top = S->base; /// 栈顶与栈底相同
    S->stacksize = StackInitSize; // 栈的最大长度等于初始长度
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11

3.销毁栈

代码如下（示例）：

// 栈顶栈底指针置为NULL，长度置为0
Status DestroyStack(SqStack* S) {
    free(S->base);
    S->base = S->top = NULL;
    S->stacksize = 0;
    return 1;
}
1
2
3
4
5
6
7

4.判定S是否为空

Status StackEmpty(SqStack* S) {
    return S->base == S->top;//判断栈顶指针与栈底指针是否相同
}
1
2
3

5.求栈的长度

Status StackLength(SqStack* S) {
    if (S->top == S->base) {
        return 0;
    }
    return (Status)(S->top - S->base);//栈顶减去栈底指针即为栈的长度
}
1
2
3
4
5
6

6.取栈顶元素

Status GetTop(SqStack* S, int &e) {
    if (S->top == S->base) {
        return 0;
    }
    e = *(S->top - 1);
    return e;
}
1
2
3
4
5
6
7

7.遍历打印栈

Status TraverseStack(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

8.入栈操作

Status Push(SqStack* S, int &e) {
    // 若栈的最大长度不会够用时，重新开辟，增大长度
    if (S->top - S->base >= S->stacksize) {
        S->base = (ElemType*)realloc(S->base, (S->stacksize + StackIncrement) * sizeof(ElemType));
        if (!S->base) {
            return 0;
        }
        // 栈顶指针为栈底指针加上栈之前的最大长度
        S->top = S->base + S->stacksize;
        // 栈当前的最大长度等于栈之前的最大长度与增加的长度之和
        S->stacksize += StackIncrement;
    }
    *S->top++ = e; // 先赋值，后栈顶指针上移
    return e;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9.出栈操作

 Status Pop(SqStack* S, int &e) {
   if (S->base == S->top) {
       return 0;
   }
   e = *--S->top;  // 栈顶指针先下移，后赋值
   return e;
}
1
2
3
4
5
6
7

---

三，完整代码

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

#define StackInitSize 10 // 初始化栈的最大长度
#define StackIncrement 10 // 若栈最大空间不够时，需要增加的长度
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType* base; // 栈底指针
    ElemType* top; // 栈顶指针
    int stacksize; // 栈的最大长度
} SqStack;

// 初始化栈
Status InitStack(SqStack *S) {
    // 分配初始空间
    S->base = (ElemType*)malloc(StackInitSize * sizeof(ElemType));
    if (!S->base) {
        exit(0);
    }
    S->top = S->base; /// 栈顶与栈底相同
    S->stacksize = StackInitSize; // 栈的最大长度等于初始长度
    return 1;
}

// 判断栈是否为空，只需要判断栈顶指针与栈底指针是否相同即可
Status StackEmpty(SqStack* S) {
    return S->base == S->top;
}

//获取栈的实际长度，栈顶减去栈底指针即为栈的长度
Status StackLength(SqStack* S) {
    if (S->top == S->base) {
        return 0;
    }
    return (Status)(S->top - S->base);
}

// 获取栈顶的元素，参数e用来存放栈顶的元素
Status GetTop(SqStack* S, int  &e) {
    if (S->top == S->base) {
        return 0;
    }
    e = *(S->top - 1);
    return e;
}

// 进栈，参数e是要进栈的元素
Status Push(SqStack* S, int  &e) {
    // 若栈的最大长度不会够用时，重新开辟，增大长度
    if (S->top - S->base >= S->stacksize) {
        S->base = (ElemType*)realloc(S->base, (S->stacksize + StackIncrement) * sizeof(ElemType));
        if (!S->base) {
            return 0;
        }
        // 栈顶指针为栈底指针加上栈之前的最大长度
        S->top = S->base + S->stacksize;
        // 栈当前的最大长度等于栈之前的最大长度与增加的长度之和
        S->stacksize += StackIncrement;
    }
    *S->top++ = e; // 先赋值，后栈顶指针上移
    return e;
}

// 出栈，参数e用来存放出栈的元素
Status Pop(SqStack* S, int &e) {
    if (S->base == S->top) {
        return 0;
    }
    e = *--S->top; // 栈顶指针先下移，后赋值
    return e;
}

// 销毁栈，释放栈空间，栈顶栈底指针置为NULL，长度置为0
Status DestroyStack(SqStack* S) {
    free(S->base);
    S->base = S->top = NULL;
    S->stacksize = 0;
    return 1;
}

// 遍历栈，依次打印每个元素
Status TraverseStack(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;

    InitStack(S);

    printf("输入栈的长度:\n");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d", &e);
        Push(S, e);
    }
    printf("是否为空栈\n");

    if (StackEmpty(S)) {
        printf("Yes!\n");
    }
    else {
        printf("No!\n");
    }
    printf("栈的长度是 %d.\n", StackLength(S));

    printf("遍历这个栈:\n");
    TraverseStack(S);

    GetTop(S, e);
    printf("栈顶元素为 %d.\n", e);

    printf("输入一个入栈的数 :\n");
    scanf("%d", &e);
    Push(S, e);
    printf("新的栈为 :\n");
    TraverseStack(S);

    printf("删除栈顶的数 : ");
    e = Pop(S, e);
    printf("%d\n", e);

    printf("新的栈为 :\n");
    TraverseStack(S);

    printf("销毁栈 :\n");
    DestroyStack(S);
    TraverseStack(S);

    return 0;
}
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

---

四，栈的应用

思路如下：
1.利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。
2.在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
(1)当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
(3)算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

代码如下:

bool isValid(char * s){
    int length = strlen(s);     //求出字符串s的长度
    
    char Stack[length];         //定义一个顺序栈
    int top = -1;               //初始化栈

    //从左往右扫描字符串s
    for(int i = 0; i < length; i++){                        
        if(s[i] == '(' || s[i] == '[' || s[i] == '{'){    
         //扫描到“左括号”
            Stack[++top] = s[i];                           
         //将“左括号”入栈
        }else{ 
            if(top == -1)
                return false;           
       //扫描到“右括号”且栈为空，则括号匹配失败（“右括号”为单身）

            char topElem; 
            topElem = Stack[top--];     
            //出栈一个元素并赋值给topElem
            if(s[i] == ')' && topElem != '(')
                return false;                   //左右括号不匹配
            if(s[i] == ']' && topElem != '[')
                return false;                   //左右括号不匹配
            if(s[i] == '}' && topElem != '{')
                return false;                   //左右括号不匹配
        }
    }

    if(top != -1)
        return false;    
      //扫描到完字符串s后栈不空，则括号匹配失败（“左括号”为单身）
    return true;
   
}
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