数据结构之"栈"

栈的一个实际需求

请输入一个表达式
计算式:[7 * 2 * 2-5+1-5+3-3] 点击计算【如下图】

请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 -5, 但是计算机怎么理解这个算式的(对计算机而言， 它接收到的就是一个字符串)， 我们讨论的是这个问题。 -> 栈

栈的介绍

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

栈的应用场景

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

栈的快速入门

用数组模拟栈的使用

• 用数组模拟栈的使用， 由于栈是一种有序列表， 当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈， 入栈等操作。

实现思路分析,并画出示意图

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210527131238188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5fbHVxaW5nbmlhbg==,size_16,color_FFFFFF,t_70

代码实现

package DataStructures.stack;

/**
 * 用数组模拟栈
 */
public class ArrayStackDome {
    public static void main(String[] args) {
        //test
        ArrayStack stack = new ArrayStack(4);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("栈顶数据为："+stack.pop());
        stack.list();

    }
}
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack;//数组，用来模拟栈
    private int top = -1;//top 表示栈顶
    //创建构造器
    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    /**
     * 栈满
     */
    public boolean isFull(){
        return top == maxSize - 1;
    }
    /**
     * 栈空
     */
    public boolean isEmpty(){
        return top == -1;
    }
    /**
     * 入栈
     */
    public void push(int value){
        //首先判断是否为满
        if (isFull()){
            System.out.println("此栈已满！无法加入数据。");
        }
        top++;
        stack[top] = value;
    }
    /**
     * 出栈,栈顶数据返回
     */
    public int pop(){
        //首先判断是否为空
        if (isEmpty()){
            throw new RuntimeException("数据为空");
        }
        int value = stack[top];
        top--;
        return value;
    }
    /**
     * 显示数据
     */
    public void list(){
        if (isEmpty()) {
            throw new RuntimeException("数据为空");
        }
        //从栈顶开始打印数据
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
    /**
     * 判断计算符号优先级(假定返回的数字越大，计算的优先级越高)
     */
    public int priority(char oper) {
        if (oper == '+' || oper == '-'){
            return 0;
        }else if (oper == '*' || oper == '/'){
            return 1;
        }else {
            return -1;
        }
    }
    /**
     * 判断是数字还是符号
     */
    public boolean isOper(char val){
        return val == '+' || val == '-' || val == '*' || val == '/';
    }
    /**
     * 计算方法
     */
    public int cal(int num1,int num2,char oper){
        int res = 0;
        switch (oper){
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;//note:顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;//note:顺序
                break;
        }
        return res;
    }
    /**
     * 显示栈顶数据（不出栈）
     */
    public int peek(){
        return stack[top];
    }
}

栈实现综合计算器(中缀表达式)

使用栈来实现综合计算器

思路分析(图解)

代码实现

代码实现

package DataStructures.stack;

/**
 * @PackgeName: DataStructures.stack
 * @ClassName: Calculator
 * @Author: 小天才
 * Date: 2021/5/26 9:44
 * project name: 算法和数据结构
 * @Version: 0.0.1
 * @Description: 计算器
 */
public class Calculator {
    public static void main(String[] args) {
        //根据之前模拟的栈完成
        String expression = "90+2*6-2*12/12";
        //创建两个栈（数栈，符号栈）
        ArrayStack numStack = new ArrayStack(10);
        ArrayStack poerStack = new ArrayStack(10);
        //定义索引用于扫描数值
        int index = 0;
        int num1 = 0;//接收计算数值
        int num2 = 0;
        char oper = ' ';//接收符号
        char ch = ' ';//保存接收的符号
        int res = 0;
        String keepNumber = "";//用于拼接多位数

        //开始循环扫描
        while (true){
            //单独取消计算式中的每一个值
            ch = expression.substring(index,index + 1).charAt(0);
            //判断ch是什么做出相应的操作
            if (poerStack.isOper(ch)){//如果是运算符
                //判断栈是否为空
                if (!poerStack.isEmpty()){
                    //判断优先级
                    if (poerStack.priority(ch) <= poerStack.priority((char) poerStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = (char) poerStack.pop();
                        res = numStack.cal(num1,num2,oper);
                        //结果入数栈
                        numStack.push(res);
                        //当前符号入符号栈
                        poerStack.push(ch);
                    }else {
                        //如果当前符号优先级大于栈内符号优先级
                        //直接入栈
                        poerStack.push(ch);
                    }

                }else {
                    poerStack.push(ch);
                }
            }else {//如果是数,直接入数栈
                //numStack.push(ch - 48);
                //如果是最后一位直接入栈
                if (index == (expression.length() - 1) ){
                    numStack.push(ch);
                }else {
                    keepNumber = keepNumber + ch;
                    //判断下一个是不是数字
                    if(poerStack.isOper(expression.substring(index + 1,index + 2).charAt(0))){
                        numStack.push(Integer.parseInt(keepNumber));
                        keepNumber = "";
                    }
                }

            }
            index++;
            if (index>=expression.length()){
                break;
            }
        }
        while (true){
            //如果符号栈为空则会得到计算结果
            if (poerStack.isEmpty()){
                break;
            }else {
                num1 = numStack.pop();
                num2 = numStack.pop();
                oper = (char) poerStack.pop();
                res = numStack.cal(num1,num2,oper);
                numStack.push(res);
            }
        }
        System.out.printf("表达式%s=%d",expression,numStack.pop());

    }
}

逆波兰计算器

我们完成一个逆波兰计算器， 要求完成如下任务:

1. 输入一个逆波兰表达式(后缀表达式)， 使用栈(Stack), 计算其结果
2. 支持小括号和多位数整数， 因为这里我们主要讲的是数据结构， 因此计算器进行简化， 只支持对整数的计算。

思路分析

• 例如: (3+4)× 5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
  1. 从左至右扫描， 将 3 和 4 压入堆栈；
  2. 遇到+运算符， 因此弹出 4 和 3（4 为栈顶元素， 3 为次顶元素） ， 计算出 3+4 的值， 得 7， 再将 7 入栈；
  3. 将 5 入栈；
  4. 接下来是× 运算符， 因此弹出 5 和 7， 计算出 7× 5=35， 将 35 入栈；
  5. 将 6 入栈；
  6. 最后是-运算符， 计算出 35-6 的值， 即 29， 由此得出最终结果

代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @PackgeName: DataStructures.stack
 * @ClassName: PolandNotation
 * @Author: 小天才
 * Date: 2021/5/26 16:14
 * project name: 算法和数据结构
 * @Version: 0.0.1
 * @Description: 逆波兰表达式
 */
public class PolandNotation {
    public static void main(String[] args) {
        String expression = "1+((30+3)*4)-5";
        System.out.println("中缀表达式为："+expression);
        List<String> reversePolishNotation = getReversePolishNotation(expression);
        System.out.println("后缀表达式为："+reversePolishNotation);
        int calculate = calculate(reversePolishNotation);
        System.out.println("计算结果为:"+calculate);

    }
    //将逆波兰表达式的数据写入列表中
    public static List<String> getListString(String suffixExpression){
        ArrayList<String> strings = new ArrayList<>();
        //按照空格分割
        String[] split = suffixExpression.split(" ");
        for (String s : split) {
            strings.add(s);
        }
        return strings;
    }
    //完成逆波兰表达式的扫描
    public static int calculate(List<String> stringList){
        //创建一个栈
        Stack<String> strings = new Stack<>();
        int res = 0;
        //遍历list
        for (String s : stringList) {
            //这里使用正则表达式去除数
            if (s.matches("\\d+")){//匹配多位数
                //数字入栈
                strings.push(s);
            }else {//如歌是数值
                //去除栈中的数值（两个）进行计算计算后入栈
                int num2 = Integer.parseInt(strings.pop());
                int num1 = Integer.parseInt(strings.pop());

                switch (s){
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                }
                strings.push(res + "");
            }
        }
        return Integer.parseInt(strings.pop());
    }
}

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

• 大家看到， 后缀表达式适合计算式进行运算， 但是人却不太容易写出来， 尤其是表达式很长的情况下， 因此在开发中， 我们需要将 中缀表达式转成后缀表达式。

具体步骤如下:

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

举例说明:

• 将中缀表达式“1+((2+3)× 4)-5” 转换为后缀表达式的过程如下
• 因此结果为 :"1 2 3 + 4 × + 5 – "

如图

代码实现中缀表达式转为后缀表达式

思路分析

代码实现

package DataStructures.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @PackgeName: DataStructures.stack
 * @ClassName: PolandNotation
 * @Author: 小天才
 * Date: 2021/5/26 16:14
 * project name: 算法和数据结构
 * @Version: 0.0.1
 * @Description: 逆波兰表达式
 */
public class PolandNotation {
    public static void main(String[] args) {
        String expression = "1+((30+3)*4)-5";
        System.out.println("中缀表达式为："+expression);
        List<String> reversePolishNotation = getReversePolishNotation(expression);
        System.out.println("后缀表达式为："+reversePolishNotation);
        int calculate = calculate(reversePolishNotation);
        System.out.println("计算结果为:"+calculate);

    }
    //将逆波兰表达式的数据写入列表中
    public static List<String> getListString(String suffixExpression){
        ArrayList<String> strings = new ArrayList<>();
        //按照空格分割
        String[] split = suffixExpression.split(" ");
        for (String s : split) {
            strings.add(s);
        }
        return strings;
    }
    //完成逆波兰表达式的扫描
    public static int calculate(List<String> stringList){
        //创建一个栈
        Stack<String> strings = new Stack<>();
        int res = 0;
        //遍历list
        for (String s : stringList) {
            //这里使用正则表达式去除数
            if (s.matches("\\d+")){//匹配多位数
                //数字入栈
                strings.push(s);
            }else {//如歌是数值
                //去除栈中的数值（两个）进行计算计算后入栈
                int num2 = Integer.parseInt(strings.pop());
                int num1 = Integer.parseInt(strings.pop());

                switch (s){
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                }
                strings.push(res + "");
            }
        }
        return Integer.parseInt(strings.pop());
    }
    //中缀表达式转后缀表达式（逆波兰表达式）
    public static List<String> getReversePolishNotation(String expression){
        //先将表达式写入列表
        ArrayList<String> midStrings = new ArrayList<>();
        int i = 0;//用于遍历字符串
        String str;//用于拼接多位数
        char ch;//每历遍到一个字符就放入
        do {
            //如果是非数字压入s1
            if ((ch = expression.charAt(i)) < 48 || (ch = expression.charAt(i)) > 57 ){
                midStrings.add(ch+"");
                i++;
            }else {//如果是一个数考虑多位数问题
                str = "";
                while (i < expression.length() && (ch=expression.charAt(i)) >= 48 && (ch=expression.charAt(i)) <= 57){
                    str =str + ch+ "";//先将当前字符拼接
                    i++;
                }
                midStrings.add(str);
            }
        }while (i<expression.length());
        //转逆波兰表达式
        /**
         * 1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
         * 2) 从左至右扫描中缀表达式；
         * 3) 遇到操作数时，将其压s2；
         * 4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
         * 1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
         * 2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
         * 3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
         * 5) 遇到括号时：  (1) 如果是左括号“(”，则直接压入s1 (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
         * 6) 重复步骤2至5，直到表达式的最右边
         * 7) 将s1中剩余的运算符依次弹出并压入s2
         * 8)  依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
         */
        Stack<String> s1 = new Stack<>();//符号栈
        ArrayList<String> s2 = new ArrayList<>();
        for (String item : midStrings) {
            if (item.matches("\\d+")){//扫描到数字
                s2.add(item);
            }else if (item.equals("(")){
                s1.push(item);
            }else if (item.equals(")")){
                while (!s1.peek().equals("(")){
                    String pop = s1.pop();
                    s2.add(pop);
                }
                s1.pop();//消除（
            }else {
                if (s1.isEmpty() || s1.peek().equals("(")){
                    s1.push(item);
                }else if (Operation.getValue(item) > Operation.getValue(s1.peek())){
                    s1.push(item);
                }else {
                    s2.add(s1.pop());
                    s1.push(item);
                }
            }
        }
        while (s1.size() != 0){
            s2.add(s1.pop());
        }
        midStrings = s2;

        return midStrings;
    }
    //比较优先级
}
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    //写一个方法， 返回对应的优先级数字
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符");
                break;
        }
        return result;
    }
}

原文链接:https://blog.csdn.net/ruan_luqingnian/article/details/117326396