1. 栈的数据结构
栈是限定仅在表尾进行插入和删除操作的线性表
允许插入和删除的一端称为栈顶(Top),另一端称为栈底,不含任何数据元素的栈称为空栈,栈又称为后进先出的线性表
image
2.栈的实现
1. 顺序方式
只能进行尾插和尾删
image
应用Stack继承自Vector(可以说Vector是加上线程安全的ArrayList)
2. 链式方式
image
插入方式
image
3. 逆波兰表达式
知识:
a/2和a>>1位移行效率会更高
a2和a<<1位移效率高
为什么:
/和需要六个运算集,位移只需要一个运算集
为什么有6个计算集:
高级语言计算表达式不是简单的计算,使用逆波兰表达式
1.例使用逆波兰表达式计算9+(3-1)*3+10/2(中缀表达式)
c和java会将中缀表达式,转成后缀表达式进行计算
中缀表达式转成后缀表达式
横向表示栈顶,竖向表示取到的操作符
规则:数字输出,运算法进栈,括号匹配出栈,比栈顶优先级低就出栈(表中1>2)
image
使用:
- 9直接输出
- +号进栈,栈底默认有一个优先级最高的#(如果+号优先级比#高就出栈,如果低就直接往里面放)
- "("直接放到栈里面,这时候栈里面数据是#,+,(
- 3直接输出,这时候输出有9 3
- "-"号进栈
- 1输出 9 3 1
- )与(匹配,栈中()中的-直接出栈,这时候栈中剩#,+ 9 3 1 -
- *比+号优先级高,直接进栈
- 3输出 9 3 1 - 3
- +号比栈顶的优先级低,“”就出栈 9 3 1 - 3 *,+号和+号比优先级也高,也出来 9 3 1 - 3 * +
- 数字10直接输出 9 3 1 - 3 * + 10
- / 优先级比+号高,直接放到栈里面
- 输出数字2 9 3 1 - 3 * + 10 2
- 最后把栈里的东西取出来就输出了后缀表达式 9 3 1 - 3 * + 10 2 / +
计算方法
1⃣️ 数字入栈
2⃣️ 符号就取2个进行计算,再入栈 - 数字入栈,栈中就是9 3 1,1处在栈顶
- 接下来是-号,就从栈中取俩个数字,从右向左放就是3-1,然后把计算结果放到栈里面,这时栈里面就是9,2 2处于栈顶
- *号运算符出现,就再取俩个数字,从右向左放就是6,从新放到栈里面是9,6
- +号出现,得出15放回栈里面
- 10,2入栈,栈里面就是15,10,2
- /运算符出现,栈里面改成15,5
- 最后还剩下+法,得出结果是20
2.递归
5!=54!
4!=43!这种情况可以使用递归解决
public int fact(int n) {
if (n <= 1) {
return 1;
} else {
return n * fact(n - 1);
}
}
1.使用递归玩转汉诺塔游戏
/**
* 汉诺塔游戏
*
* @param n 盘子的个数
* @param start 开始的柱子
* @param middle 中介柱子
* @param end 放结果的柱子
*/
public static void hanoi(int n, int start, int middle, int end) {
if (n <= 1) {
System.out.println(start + "---" + end);
} else {
//通过结果的柱子，把盘子移到中间的柱子上
hanoi(n - 1, start, end, middle);
//把最下面的大盘子移动到放结果的柱子上
System.out.println(start + "---" + end);
//把剩下的盘子从中间柱子通过第一个柱子移到最后一个柱子上
hanoi(n - 1, middle, start, end);
}
}
