栈

• 栈
  • 基本介绍
  • 应用场景
  • 实现思路
  • 代码实现
    • 使用数组模拟栈
    • 使用双链表模拟栈
  • 使用栈实现综合计算器
    • 思路分析
    • 代码实现
  • 前缀、中缀、后缀表达式（逆波兰表达式）
    • 前缀表达式
    • 中缀表达式
    • 后缀表达式
  • 中缀表达式转后缀表达式
    • 代码实现

基本介绍

1. 栈(stack)是一个先入后出(FILO-First ln Last Out)的有序列表。
2. 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另—端为固定的一端，称为栈底(Bottom)。
3. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
4. 出栈(pop)，入栈(push)

应用场景

1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3. 表达式的转换与求值（实际解决）。
4. 二叉树的遍历（中缀表达式转后缀表达式）。
5. 图形的深度优先(depth—first)搜索法。

实现思路

1. 使用数组模拟栈
2. 定义一个 top 来表示栈顶，初始化为 -1
3. 入栈的操作：当有数据加入到栈时，
   top++; stack[top] = data;
4. 出栈的操作：
   int value = stack[top]; top--; return value;

代码实现

使用数组模拟栈

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);

        while (loop) {
            System.out.println("show: 显示栈");
            System.out.println("push: 入栈");
            System.out.println("pop: 显示栈");
            System.out.println("exit: 退出");
            System.out.println("请输入你的选择");
            key = scanner.next();
            switch (key) {
                case "show":
                    arrayStack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int value = scanner.nextInt();
                    arrayStack.push(value);
                    break;
                case "pop":
                    try {
                        int res = arrayStack.pop();
                        System.out.printf("出栈的数据是 %d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class ArrayStack {
    private int maxSize; // 栈的大小
    private int[] stack; // 数组模拟栈
    private int top = -1; // 栈顶

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
    }

    // 判断栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

    // 栈空
    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈-push
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈-pop
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 遍历栈，从栈顶开始遍历
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空，没有数据");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }
}

使用双链表模拟栈

package com.yur.stack;

public class LinkedListStackDemo {
    public static void main(String[] args) {
        // 测试
        LinkedListStack stack = new LinkedListStack();
        // 入栈
        stack.push(new LinkedListStackNode(1));
        stack.push(new LinkedListStackNode(2));
        stack.push(new LinkedListStackNode(3));
        stack.list();
        // 出栈
        stack.pop();
        stack.pop();
        stack.list();
    }
}

class LinkedListStack {
    private LinkedListStackNode top = new LinkedListStackNode(-1);

    // 判断栈空
    public boolean isEmpty() {
        return top.getVal() == -1;
    }

    // 入栈
    public void push(LinkedListStackNode node) {
        top.next = node;
        node.pre = top;
        top = node;
    }

    // 出栈
    public void pop() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        System.out.println(top.getVal()+" 出栈");
        top = top.pre;
        top.next = null;
    }

    // 遍历
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        LinkedListStackNode temp = top;
        while (true) {
            System.out.println(temp.getVal());
            if (temp.pre.getVal() == -1) {
                break;
            }
            temp = temp.pre;
        }
    }
}

// 节点类
class LinkedListStackNode {
    private int val;
    public LinkedListStackNode next;
    public LinkedListStackNode pre;

    public LinkedListStackNode(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }
}

使用栈实现综合计算器

思路分析

1. 创建两个栈，分别存放数字和符号；
2. 通过一个index值（索引），来遍历我们的表达式；
3. 如果是一个数字，就直接入数栈；
4. 如果扫描到是一个符号，就分如下情况：

• 如果发现当前的符号栈为空，就直接入栈；
• 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈（这里存在问题）；
• 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈；

5. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行；
6. 最后在数栈只有一个数字，就是表达式的结果；

代码实现

public class Calculator {
    public static void main(String[] args) {
        String expression = "7-9*8+2*6";
        // 创建两个栈，分别存放数字和符号
        ArrayStackForCal numStack = new ArrayStackForCal(10);
        ArrayStackForCal operStack = new ArrayStackForCal(10);

        // 通过一个`index`值（索引），来遍历我们的表达式
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' '; // 保存每次扫描的字符
        String keepNum = ""; // 拼接多位数字
        while (true) {
            ch = expression.substring(index, index + 1).charAt(0);
            // 如果发现扫描到一个符号，就分如下情况
            if (operStack.isOper(ch)) {
                // 如果符号栈有操作符，就进行比较，
                if (!operStack.isEmpty()) {
                    // 如果当前的操作符的优先级小于或者等于栈中的操作符，
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        // 从数栈中`pop`出两个数，在从符号栈中`pop`出一个符号，
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        // 进行运算
                        res = numStack.cal(num1, num2, oper);
                        // 将得到结果，入数栈
                        numStack.push(res);
                        // 将当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        // 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
                        operStack.push(ch);
                    }
                } else {
                    // 如果发现当前的符号栈为空，就直接入栈；
                    operStack.push(ch);
                }
            } else {
                // 分析思路
                // 1.当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                // 2，在处理数，需要向expression的表达式的index后再看一位，如果是数就进行扫描，如果是符号才入栈
                // 3. 此我们需要定义一个变量字符串,用于拼接
                keepNum += ch;
                // 如果ch已经是expression的最后一位,就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(keepNum));
                        // 清空keepNum！！！
                        keepNum = "";
                    }
                }
            }
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        while (true) {
            // 如果符号栈为空，计算结束，此时数栈只有一个元素即为结果
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = operStack.cal(num1, num2, oper);
            numStack.push(res); // 入栈
        }
        System.out.printf("表达式 %s = %d\n", expression, numStack.pop());
    }
}

// 供计算机调用的数组栈
class ArrayStackForCal {
    private int maxSize; // 栈的大小
    private int[] stack; // 数组模拟栈
    private int top = -1; // 栈顶

    public ArrayStackForCal(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
    }

    // 判断栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

    // 栈空
    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈-push
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈-pop
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 遍历栈，从栈顶开始遍历
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空，没有数据");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }

    // 返回栈顶值
    public int peek() {
        return stack[top];
    }

    // 返回运算优先级
    public int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;
        }
    }

    // 判断是不是一个运算符
    public boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    // 计算方法
    public int cal(int num1, int num2, int oper) {
        int res = 0;
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1; // 注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }
}

前缀、中缀、后缀表达式（逆波兰表达式）

前缀表达式

运算符再数字之前，从右向左扫描

例如: $(3+4)×5-6$ 对应的前缀表达式就是 $-×+3456$

中缀表达式

例如: $(3+4)×5-6$

后缀表达式

运算符再数字之后，从左向右扫描

例如: $(3+4)×5-6$ 对应的后缀表达式就是 $34+5×6-$

中缀表达式转后缀表达式

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

代码实现

public class PolandNotation {
    public static void main(String[] args) {
        // 定义中缀表达式
        String expression = "1+((2+3)*4)-5";
        // 中缀表达式转为 list
        List<String> expressionList = toInfixExpression(expression);
        // 中缀表达式list转后缀表达式list
        List<String> suffixExpressionList = parseSuffixExpressionList(expressionList);
        System.out.println("后缀表达式："+suffixExpressionList);
        System.out.println(expression + "=" + Calculator(suffixExpressionList));
    }

    // 中缀表达式list转后缀表达式list
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        Stack<String> s1 = new Stack<>(); // 运算符栈
        Stack<String> s2 = new Stack<>(); // 存储中间结果
        List<String> res = new ArrayList<>();
        for (String item : ls) {
            if (item.matches("\\d+")) {
                // 遇到操作数时，将其压s2
                s2.push(item);
            } else if (item.equals("(")) {
                // 如果是左括号 “(”，则直接压入s1
                s1.push(item);
            } else if (item.equals(")")) {
                // 如果是右括号 “)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (true) {
                    String num = s1.pop();
                    if (num.equals("(")) {
                        break;
                    } else {
                        s2.push(num);
                    }
                }
            } else {
                while (true) {
                    // 遇到运算符时，比较其与 s1栈顶运算符的优先级
                    // 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
                    // 否则，若优先级比栈顶运算符的高，也将运算符压入s1;
                    if (s1.empty() || s1.peek().equals("(") || priority(item) > priority(s1.peek())) {
                        s1.push(item);
                        break;
                    } else {
                        // 否则，将 s1栈顶的运算符弹出并压入到 s2中，再次转到(4.1)与 s1中新的栈顶运算符相比较
                        s2.push(s1.pop());
                    }
                }
            }
        }
        while (!s1.empty()) {
            s2.push(s1.pop());
        }
        while (!s2.empty()) {
            res.add(s2.pop());
        }
        // 反转list
        Collections.reverse(res);
        return res;
    }

    // 计算后缀表达式
    public static int Calculator(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());// 栈顶
                int num2 = Integer.parseInt(stack.pop());// 次顶
                int res;
                switch (item) {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num2 - num1;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num2 / num1;
                        break;
                    default:
                        throw new RuntimeException("运算符出错");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    // 中缀表达式转为 list
    public static List<String> toInfixExpression(String s) {
        List<String> ls = new ArrayList<>();
        int i = 0;
        String str; // 多位数拼接
        char c; // 每次遍历的字符
        do {
            // 如果是字符
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;
            } else {
                // 如果是数字
                str = ""; // 'o' [48]-> '9'[57]
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }

    // 返回运算优先级
    public static int priority(String oper) {
        if (oper.equals("*") || oper.equals("/")) {
            return 1;
        } else if (oper.equals("+") || oper.equals("-")) {
            return 0;
        } else {
            return -1;
        }
    }
}