线性表
栈
什么是栈
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
LIFO(last in first out)结构
栈的顺序储存结构的实现
首先定义一个变量top来指示栈顶，top变量随着数据的入栈和出栈不断的变化。但是变化的范围需要在栈的长度范围之内
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| struct stack{
int data[MAXN];
int top;
}sqstack;
push(stack *s, int x){
if(s->top == MAXN - 1) return ERROR;
s->top++;
s->data[s->top] = x;
return OK;
}
pop(stack *s, int *x){
if(s->top == -1) return ERROR;
*x = s->data[s->top];
top--;
return OK;
}
|
两个栈共享空间
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
| struct stack{
int data[MAXN];
int top1;
int top2;
}sqstack;
push(stack *s, int x, int num){
if(s->top1 + 1 == s->top2) return ERROR;
if(num == 1){
s->data[++s->top1] = x;
}
else{
s->data[--s->top2] = x;
}
return OK;
}
pop(stack *s, int *x, int num){
if(num == 1){
if(s->top1 == -1) return ERROR;
*x = s->data[s->top1--];
}
else{
if(s->top2 == MAXN) return ERROR;
*x = s->data[s->top2++];
}
return OK;
}
|
栈的链式储存结构的实现
栈的应用
递归
操作系统在执行递归函数的时候，将每层递归函数的局部变量，参数值和返回地址压入栈，腾出寄存器进行下一层递归。在递归结束的退回阶段再将每层的结果出栈。
四则表达式求值
后缀（逆波兰）表示法定义
对于“9+(3-1)×3+10÷2”，用后缀表示法则变为：“9 3 1-3*+10 2/+”
即所有的符号都是在要运算数字的后面出现。
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
中缀表达式转后缀表达式
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。