title: "栈"
date: 2015-05-09 23:24:43
categories: 数据结构
tags: [data-structure,foundation]
声明：对于本篇文章表格部分不清晰者，请查看 http://www.jianshu.com/p/d34c901e6506
概念
- 特殊的线性表；
- 后进先出，栈底先进，栈顶后进；
LIFO( Last In First Out ) - 插入和删除操作都在栈顶；
应用场景
- 需要保存前边数据元素的情况；
- 比如：访问轨迹、撤销命令、递归、后缀表达式（逆波兰式）等。
顺序存储
- 满足线性表顺序存储的特性；
- 顺序栈；
- 用数组实现，底位是栈底，高位是栈顶。
-
top变量指示栈顶元素在数组中的位置；（可变）。
FILO - __ 两栈共享空间 __ ：
- 用一个数组存两个栈；
- A栈栈底始端（下标=0），B栈栈底末端（下标=n-1）；
- 两栈增加元素，向中间延伸；
- 两栈
数据类型必须相同；
FILO-share
链式存储
- 满足线性表链式存储特性；
- 链栈；
- 无头结点，头指针=栈顶指针
top； - 无栈满的情况（除非内存满）；
-
top=NULL 代表空；
FILO-chain
栈的应用
斐波那契数列
| 经过的月数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 兔子对数 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
- 兔子在出生两个月后有繁殖能力。
- 一对兔子每个月能生出一对小兔子（假设所有兔子都不死），那么一年后会生出多少对兔子？
- n=0; f(n)=0;
- n=1; f(n) = 1;
- n>1; f(n) = f(n-2)+f(n-1);
- 代码实现，以下两种方式分别是循环、递归：
#include<stdio.h>
int main()
{
int i;
int a[40];
a[0] = 0;
a[1] = 1;
printf("%d\n", a[0]);
printf("%d\n", a[1]);
for(i=2; i<13; i++)
{
a[i] = a[i-1] + a[i-2];
printf("%d\n", a[i]);
}
}
#include<stdio.h>
int Fbi(int i)
{
if( i<2 )
{
return i == 0 ? 0 : 1;
}
return Fbi(i-1) + Fbi(i-2);
}
int main()
{
int i;
for(i=0; i<13; i++)
{
printf("%d\n", Fbi(i));
}
}
四則运算表达式（逆波兰式）求值
- 标准的四則表达式 9 + ( 8 - 2 ) / 3 * 2 + 10 / 5，称为
中缀表达式； - 中缀表达式转为 后缀表达式的规则：
- 从左到右遍历中缀表达式的每个元素；
- 遍历过程中
数字输出（成为后缀表达式的一部分）； - 遍历过程中
符号，判断与栈顶符号的优先级，如果是右括号或优先级<=栈顶符号，則栈顶元素（符号）依次出栈并输出，直到遇到栈顶元素比自己优先级高为止，否则栈顶依次全部输出； - 将当前符号进栈，最终输出为后缀表达式；
- 总结：
遇见数字就输出，遇见符号就进出栈；
- 实例：中缀表达式 9 + ( 8 - 2 ) / 3 * 2 + 10 / 5 转换为后缀表达式。
| 后缀串 | 操作符 |
|---|---|
| 9 | _ 输出 9 _ |
| 9 | + _ 加号入栈 _ |
| 9 | + ( _ 左括号入栈 _ |
| 9 8 | + ( _ 输出 8 _ |
| 9 8 | + ( - _ 减号 入栈 _ |
| 9 8 2 | + ( - _ 输出 2 _ |
| 9 8 2 - | + _ 遇见右括号，括号内减号出栈输出 _ |
| 9 8 2 - | + / _ 除号 入栈 _ |
| 9 8 2 - 3 | + / _ 输出 3 _ |
| 9 8 2 - 3 / | + * _ 乘优先级=栈顶除，除出栈，乘优先级>加，+不出栈，乘入栈 _ |
| 9 8 2 - 3 / 2 | + * _ 输出 2 _ |
| 9 8 2 - 3 / 2 * + | + _ 乘出栈，加出栈，+进栈 _ |
| 9 8 2 - 3 / 2 * + 10 | + _ 输出 10 _ |
| 9 8 2 - 3 / 2 * + 10 | + / _ 除入栈 _ |
| 9 8 2 - 3 / 2 * + 10 5 | + / _ 输出5 _ |
| 9 8 2 - 3 / 2 * + 10 5 / + | _ 最后除出栈，加出栈 _ |
转换后的后缀表达式：9 8 2 - 3 / 2 * + 10 5 / +
-
后缀表达式在计算机的运算规则如下：
- 从左到右遍历表达式每个元素；
- 遇到数字就进栈，遇到符号就将栈顶两个数字出栈，进行运算。
-
以上后缀表达式在计算机的运算过程是：
FILO-demo -
讨论板图：
stack
houzhui
houzhui
