JAVA-4.栈

14

介绍

栈的使用

public class Demo1 {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        //入栈
        stack.push("1");
        stack.push("2");
        stack.push("3");
        //出栈
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }
}
public class StackDemo {
    public static void main(String[] args) {
        //创建集合
        //1.Stack stack = new Stack();
        //2.LinkedList实现了Stack功能
        LinkedList<String> stack = new LinkedList<>();
        //入栈 ->添加
        stack.push("1");
        stack.push("2");
        stack.push("3");

        System.out.println(stack.peek());
        //出栈 ->删除
        int size = stack.size();
        //for (int i = 0; i < stack.size(); i++) 错误,会变
        for (int i = 0; i < size; i++) {
            System.out.println(stack.pop());
        }
        System.out.println("元素个数" + stack.size());
    }
}

链表和数组都可以模拟栈操作,可尝试实现。

栈的应用

中缀表达式的计算器

中缀表达式:7*2-3+2-5

实现思路:准备两个栈,一个栈中存放数字,另一个栈中存放运算符。中缀表达式存放在字符串中,我们需要从头开始读取每一个字符,当是数字时,如数字栈。当是字符时,分为两种情况:1.字符栈中无元素,直接入栈。2.字符栈中存在元素,要比较两者的优先级,栈内元素优先级低,直接入栈;栈内元素优先级高,出栈该字符并出栈数字栈的两个数字进行计算,将计算结果再入数字栈。 最后只要数字栈出栈两个数字 、字符栈出栈一个字符计算运算,再将运算结果入数字栈,重复运算知道数字栈为空栈。

如计算 3+4*2 时:

如计算 3*2-4时:

后缀表达式(逆波兰表达式)

前缀表达式:1+((2+3)*4)-5

后缀表达式:1 2 3 + 4 * + 5 -

中缀表达式转后缀表达式

初始化两个栈,一个存储运算符s1,一个存储中间结果s2。

从左到右读取中缀表达式的每一个字符,当遇到数字是压入栈s1。当遇到运算符时,比较与s1栈顶运算符的优先级,规则如下:

  • 1.如果s1为空,或栈顶元素为左括号,直接入栈。
  • 2.若优先级比栈顶元素的高,直接入栈。
  • 3.若优先级比栈顶元素低时,将栈顶元素出栈压入s2中,继续重复运算符规则的这三个条件,直到符合条件入栈。

当遇到括号时:

  • 1.如果是左括号,可以直接入栈。
  • 2.如果是右括号,依次弹出s1的栈顶运算符,压入s2,直到遇见左括号。将这一对括号丢弃。
  • 重复步骤,知道中缀表达式的最右边。
  • 将s1中剩余元素,依次出栈压入s2中。
  • 依次出栈s2中的元素,结果的逆序就是后缀表达式

后缀表达式的现实思路

由此看出中缀表达式和后缀表达式的含义:运算符的位置是在中间还是在后面。