JAVA-4.栈

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中的元素，结果的逆序就是后缀表达式

后缀表达式的现实思路：

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