github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/数据结构_栈.md
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/stack.png
定义
限定仅在表尾进行插入和删除操作的线性表
也是线性表，一种特殊的线性表
凡是那些需要临时保存前面数据元素的场景！访问轨迹、撤销命令、递归函数等等
规则
- 栈底的位置是永远不变的，栈顶执行一切操作
- 顺序存储时，指针指向栈顶
- 顺序存储时，栈的删除和添加都是在栈顶的，因此效率比普通的线性表高
- 顺序存储时，两栈可以共享空间。就是一个大数组里面包含两个栈，栈顶相对
- 链式存储时，第一个节点（不是头节点）就是栈顶，最后一个节点就是栈底
操作
入栈（栈顶）、出栈（栈顶）
应用
斐波那契数列 ----------------------------------
公式：F(n) = F(n-1)+F(n-2)
四则运算表达式（后缀表达式／逆波兰表达式） ---------------------------------------
表达式：9+(3-1)*3+10/2 （这就是中缀表达式）第一个＋记作+[1],第二个+记作+[2]
后缀表达式：931-3*+[1]102/2+[2]
| 编号 | 后缀表达式 | 运算符 | 说明 |
|---|---|---|---|
| 1 | 9 | +[1] | |
| 2 | 93 | +[1]( | |
| 3 | 931 | +[1](- | |
| 4 | 931- | +[1] | 反括号优先级 |
| 5 | 931- | +[1]* | *号优先级高于+ |
| 6 | 931-3 | +[1]* | |
| 7 | 931-3*+[1] | +[2] | +[2]的优先级小于等于原先的运算符 |
| 8 | 931-3*+[1]10 | +[2] | |
| 9 | 931-3*+[1]10 | +[2]/ | |
| 10 | 931-3*+[1]102 | +[2]/ | |
| 11 | 931-3*+[1]102/+[2] |
最后得到逆波兰式：931-3*+102/+
网友评论