数据结构(二)栈及栈的应用-使用逆波兰表达式计算,递归

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);
        }
    }