4 栈

4.1 实际需求

​ 科学计算器就是用到了栈的原理

4.2 介绍

• 英文名为：stack

• 栈是一个先进后出（First in last out）的有序列表

• 栈是 限制线性表，元素的插入和删除只能在线性表的同一端进行，允许插入和删除的一端称为变化的一端，是栈顶，另外一端为固定的一端，称为栈底。

• 根据栈的定义，最先放入栈中的元素在栈底，最后放入栈中的元素在栈顶。最先弹出的元素在栈顶，最后弹出的元素在栈底。

• 压栈(push)和弹栈(pop)的原理图

4.3 栈的经典应应用场景

• 子程序的调用：在调用子程序之前，先将下个指令的地址存入到堆栈中，直到子程序执行完再将地址取出，回到原来的程序之中
• 处理递归调用：与子程序调用的原理类似，只不过是除了存储下一个指令的地址之外，也将参数，局部变量等数据存入到堆栈中
• 表达式的转换和求值[中缀表达式转换为后缀表达式]
• 二叉树的遍历
• 图形的深度优先(depth-first)搜索法

4.4 栈的实现

4.1 使用数组

class MyStack {
    private int capacity;
    int[] array;
    int pointer = -1;
    public MyStack() { }
    public MyStack(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
    }

    // 压栈的方法(push)
    public void push(int num) {
        if (pointer == capacity - 1) {
            throw new RuntimeException("栈已满，压栈失败");
        } else {
            array[++pointer] = num;
        }

    }

    // 弹栈的方法(pop)
    public void pop() {
        if(pointer == -1) {
            throw new RuntimeException("栈已空，弹栈失败");
        } else {
            array[pointer--] = 0;
        }
    }

    // 遍历栈的方法
    public void printStack(){
        System.out.println("栈中现存的元素为：");
        for (int i = pointer; i >= 0 ; i--) {
            System.out.printf("%d\t", array[i]);
        }
    }
}

4.2 使用单向链表

class StackByList {
    ListNode header = new ListNode(-1);
    int capacity;

    public StackByList() { }
    public StackByList(int capacity) {
        this.capacity = capacity;
    }

    // 获取当前栈中元素的个数
    public int getSize() {
        ListNode p = header;
        int count  = 0;
        while(p.next != null) {
            p = p.next;
            count++;
        }
        return count;
    }

    // 往栈中添加元素的方法
    public void push(ListNode listNode) {
        ListNode p = header;
        if (this.getSize() == capacity)
            throw new RuntimeException("栈已满，无法添加更多的元素");
        listNode.next = p.next;
        p.next = listNode;
    }

    // 移除栈中元素的方法
    public void pop() {
        ListNode p = header;
        if (p.next == null)
            throw new RuntimeException("栈已空，弹栈失败");
        p.next = p.next.next;
    }

    // 打印栈中元素的方法
    public void printStack() {
        ListNode p = header;
        if (p == null || p.next == null)
            System.out.println("当前栈中没有元素");
        p = p.next;
        while (p != null) {
            System.out.printf("%d\t", p.value);
            p = p.next;
        }
    }

}

class ListNode {
    int value;
    ListNode next;

    public ListNode(int value) {
        this.value = value;
    }
    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }

    public ListNode() { }
}

4.4 使用栈完成计算器的实现

4.4.1 思路分析

• 通过一个指针来扫描这个字符串，遍历我们的表达式

• 扫描的过程中：

  • 扫描到数字就把它放到数栈中
  • 扫描到是一个符号
    • 如果符号栈为空，就直接入栈
    • 如果符号栈有操作符，当前操作符的优先级小于或者等于栈中的操作符的优先级，就需要从数栈中pop两个数，从符号栈中pop一个符号，进行计算，将得到结果，将结果push入数栈，将当前的符号push进操作符栈；如果当前的操作符的优先级大于栈中操作符的优先级，就直接将操作符压入栈中即可，不需要进行计算

• 表达式扫描完毕之后，顺序从数栈和符号栈中pop出相应的元素进行运算

• 最后数栈中只有一个数据，就是这个表达式的结果

4.4.2 代码实现

class NumsComputer{
    // 存操作符的栈
    IntStack operaStack = new IntStack(5);
    // 存操作数的栈
    IntStack numsStack = new IntStack(10);
    // 构造方法
    public NumsComputer() { }
    // 遍历字符串的方法
    public void scanString(String string) {
        char[] chars = string.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 48 && chars[i] <= 57) numsStack.push(chars[i] - '0'); // 将字符型数据转换为整数型存入
            // 在将操作符压入栈中的时候，需要抽象成一个方法
            else if (operaStack.pointer == -1) operaStack.push(chars[i]);   // 符号栈中元素为空
            else pushOperator(chars[i]);
        }
    }

    // 运算方法
    public int compute(){
        while (operaStack.pointer != -1) {
            operate(operaStack, numsStack);
        }
        int result = numsStack.pop();
        return result;
    }

    // 获取符号优先级的方法
    public static int getPriority(int c) {
        if (c == '*' || c == '/') {
            return 1;
        } else return 0;
    }

    // 操作符号压栈的方法
    public void pushOperator(char c) {
        // 如果当前运算符的优先级小于或者等于栈中的优先级
        if (getPriority('c') <= getPriority(operaStack.array[operaStack.pointer])){
            operaStack.push(c);
        } else { operaStack.push(c); } // 当前符号优先级大于栈顶的符号优先级
    }
    // 弹栈进行计算的方法
    public static void operate(IntStack operaStack, IntStack numsStack) {
        // 从数栈中弹出两个元素
        int a = numsStack.pop();
        int b = numsStack.pop();
        // 从运算符栈中弹出一个元素
        int c = operaStack.pop();
        int result = 0;
        switch (c) {
            case '+': result = b + a; break;
            case '-': result = b - a; break;
            case '*': result = b * a; break;
            case '/': result = b / a; break;
        }
        numsStack.push(result);
    }
}

class IntStack {
    private int capacity;
    int[] array;
    int pointer = -1;

    public IntStack() {
    }

    // 获取栈中元素个数
    public int getSize() {
        int count = 0;
        while (array[count] != 0)
            count++;
        return count;
    }

    public IntStack(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
    }

    // 压栈的方法(push)
    public void push(int c) {
        if (++pointer == capacity) {
            throw new RuntimeException("栈已满，压栈失败");
        }
        array[pointer] = c;

    }

    // 弹栈的方法(pop)
    public int pop() {
        if (pointer == -1) {
            throw new RuntimeException("栈已空，弹栈失败");
        } else {
            int c = array[pointer];
            array[pointer--] = 0;
            return c;
        }
    }

    // 遍历栈的方法
    public void printStack() {
        System.out.println("栈中现存的元素为：");
        for (int i = pointer; i >= 0; i--) {
            System.out.print(array[i] + "\t");
        }
    }
}

4.5 三种表达式

4.5.1 前缀表达式

1）概述

• 前缀表达式又称为波兰表达式
• 前缀表达式的运算符位于操作数之前
• 举例：(3 + 4) * 5 - 6 对应的前缀表达式为- * + 3 4 5 6

2）计算机求值

​ 从右至左扫描表达式，遇到数字的时候将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（栈顶元素和次顶元素），并将结果并入栈中，重复上述过程直到表达式最左端，最后运算的到的值即为表达式的结果。

• 从右至左扫描，将6、5、4、3压入堆栈
• 遇到 + 运算符，因此弹出3、4，计算3 + 4的值，将结果7压入栈中
• 接下来时 * 运算，弹出7 和 5 计算出7 * 5，将结果35压入栈中
• 最后时 - 运算符，计算出35 - 6的值，得到最终的结果

4.5.2 中缀表达式

1）概述

• 中缀表达式就是常见的运算表达式，例如(3 + 4) * 5 - 6
• 中缀表达式的求职是人们最熟悉的，但是中缀表达式对于计算机却是非常棘手。因此在计算中缀表达式的结果时，往往会将中缀表达式转换为其他表达式来操作，一般为后缀表达式。

4.5.3 后缀表达式

1）概述

• 后缀表达式又称为逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后
• 举例：(3 + 4) * 5 -6对应的后缀表达式为3 4 + 5 * 6 -

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fH6ygEAC-1619919934940)(E:\JavaSpace\上课截图\逆波兰表达式.png)]

2. 计算机求值

• 从左至右扫描表达式，将3 4压入栈中
• 遇到+运算符，因此弹出 4 和 3 ，计算出3 + 4的值，再将运算结果7压入栈中
• 将 5 压入栈中
• 遇到*运算符，因此将 5 和 7 弹出栈，计算出5 * 7的值，将 35 压入栈中
• 将 6 压入栈中
• 最后是 -运算，计算出35 - 6的值，29 即为计算的最终结果

4.6 逆波兰计算器的实现

4.6.1 需求

• 输入一个后缀表达式，使用栈(stack)计算其结果
• 支持小括号和多位整数

4.6.2 思路分析

见于4.5.3 2）计算机求值

4.6.3 代码实现

class PolandNotation {
    // 接收用户输入的表达式
    private String expression = null;

    // 创建数栈
    Stack<Integer> numStack = new Stack<>();

    public PolandNotation(String expression) {
        this.expression = expression;
    }

    //扫描表达式的方法
    public void compute() {
        // 将表达式的值转变为一个char数组
        char[] chars = expression.toCharArray();
        int i = 0;
        // 对整个char数组进行遍历
        while (i < chars.length) {
            // 如果扫描的是一个符号
            if (chars[i] < 48 && chars[i] > 32) {
                numStack.push(calculate(chars[i], numStack));
                i++;
            } else if (chars[i] == 32) { i++; } // 扫描到的是一个空格
            else {
                String numString = "";
                while(i < chars.length && chars[i] != 32) {
                    numString = numString + chars[i];
                    i++;
                }
                int num = Integer.parseInt(numString);
                numStack.push(num);
            }
        }

        // 只需要将此时栈中的元素弹出来即可
        int result = numStack.pop();
        System.out.println(result);
    }

    // 弹栈计算的方法
    public int calculate(char operator, Stack<Integer> numStack) {
        // 栈中弹出两个元素
        int num1 = numStack.pop();
        int num2 = numStack.pop();
        int result = 0;
        switch (operator) {
            case '+': result = num2 + num1; break;
            case '-': result = num2 - num1; break;
            case '*': result = num2 * num1; break;
            case '/': result = num2 / num1; break;
        }
        return result;
    }
}

4.6.4 将中缀表达式转换为后缀表达式

1）算法流程

• 初始化两个栈：运算符栈和s1存储中间结果的栈s2
• 从左至右扫描中缀表达式
• 遇到操作数的时候，将其压入s2
• 遇到运算符时，比较其与s1栈顶运算符的优先级
  • 如果s1为空或者栈顶运算符为左括号(，直接将此运算符入栈
  • 否则，若优先级比栈顶的运算符的优先级高，也将运算符压入栈中
  • 否则，将s1栈顶的运算符弹出并压到s2中，再将此运算符与新的运算符进行优先级的比较
• 遇到括号时
  • 如果是左括号(，直接压入到s1栈中
  • 如果是右括号)，依次弹出s1栈顶的运算符，并压入到s2中，直到遇到左括号为止，此时将这一对括号丢弃
• 重复步骤2到5，直到表达式的最右边
• 将s1剩余的运算符依次弹出并压入到s2
• 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

2）实现代码

public char[] transform(String expression){
        // 将这个中缀表达式变为一个char数组
        char[] expressChars = expression.toCharArray();
        // 初始化运算符栈
        Stack<Character> operaStack = new Stack<>();
        // 初始化队列
        CycleQueue numQueue = new CycleQueue(50);
        // 扫描中缀表达式
        int i = 0;
        while (i < expressChars.length) {
            // 如果为扫描到为一个符号
            if (expressChars[i] < 48 && expressChars[i] != ' '){
                // 如果这个符号是左括号或者符号栈为空
                if (expressChars[i] == 40 || operaStack.empty()){
                    operaStack.push(expressChars[i++]);
                } // 符号未右括号的时候将符号栈里的元素弹入到数栈之中
                else if (expressChars[i] == 41) {
                    while (true) {
                        char temp = operaStack.pop();
                        // 碰到左括号后就跳出循环
                        if (temp == 40) break;
                        else {
                            numQueue.add(temp);
                            // 这里往数栈中添加元素之后再添加空格
                            numQueue.add(' ');
                        }
                    }
                    i++;
                }
                // 判断优先级,如果当前符号的优先级大于栈顶符号的优先级，直接入栈
                else if (getPriority(expressChars[i]) > getPriority(operaStack.peek())) {
                    operaStack.push(expressChars[i]);
                    i++;
                } else {
                    // 当前运算符的优先级小于或者等于栈顶
                    while (operaStack.size() != 0 && getPriority(expressChars[i]) <= getPriority(operaStack.peek())) {
                        numQueue.add(operaStack.pop());
                        numQueue.add(' ');
                    }
                    operaStack.push(expressChars[i]);
                    i++;
                }
            } else if (expressChars[i] == 32){
                // 扫描的是一个空格
                i++;
            } else {
                // 扫描的是一个数
                while (i < expressChars.length && expressChars[i] != 32 && expressChars[i] != ')'){
                    numQueue.add(expressChars[i]);
                    i++;
                }
                numQueue.add(' ');
            }
        }
        //将操作符号栈中的元素放到队列中
        while (operaStack.size() != 0) {
            numQueue.add(operaStack.pop());
            numQueue.add(' ');
        }

        // 将队列的元素取出来放到数组中
        return numQueue.toArray();
    }