Java数据结构与算法 一2

简介: Java数据结构与算法 一2

双向链表

单链表存在问题:

  1. 只有一个方向,而双向链表可以向前或前后查找
  2. 单向链表不能自我删除,要有临时变量,双向链表可以实现自我删除

双向链表结构:


ce94518616c3abdc3623de8e7a5ebf54.png


分析双向链表的CRUD



遍历:

和单链表一样,向前或向后查找

添加:默认添加到双向链表的最后

先找到双向链表的最后的这个节点(temp)

temp. next =newHeroNode

newHeroNode.pre = temp

修改

和单向链表一样

删除

自我删除某个节点

直接找到要删除的这个节点(temp)

temp.pre.next = temp.next (temp前一个直接指向temp的后一个节点)

temp.next.pre = temp.pre

单向环形链表

应用场景


Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为:设编号为1,2,… n的n个人围坐一圈, 约定编号为k(1<=k<=n)的人从1开始报数,数到m 的那个 人出列,它的下一位又从1开始报数,数到m的那个人又出 列,依次类推,直到所有人出列为止,由此产生一个出队 编号的序列.


单向环形链表结构


1bf255e14e4671c854a319b24873bf11.png


Josehu 问题 分析

先构成一个有n个结点的单循环链表, 然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点 的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束


  • n = 5 :有五个人
  • k = 1:从第一个人开始报数
  • m = 2 ,数两次

出队列报数顺序:

2 =》4 =》1=》5 =》3



分析思路

  1. 先创建第一个节点,让first指向该节点,并形成环形
  2. 后面让我们每创建一个新的节点,把该节点,加入到已经有的环形链表中



遍历环形链表
  1. 先让一个指针(变量)curBoy ,指向first节点
  2. 通过while循环遍历该环形链表curBoy.next = first


出队顺序


创建一个指针(变量)helper,开始指向环形链表的最后一个节点

报数前,先让 first 和 helper 移动 k - 1 次

报数时,让first 和 helper 指针同时移动 m - 1 次

将 first 指向这个小孩节点出圈

first = first.next

helper.next = first

原来的节点没有了任何的指向就会被垃圾回收

package com.linkedlist;
/**
 * @author Kcs 2022/8/10
 */
public class Josepfu {
    public static void main(String[] args) {
        //环形链表测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        //创建五个小孩节点
        circleSingleLinkedList.addBoy(100);
        //显示
        circleSingleLinkedList.showBoy();
        //出圈
        circleSingleLinkedList.countBoy(1, 2, 100);
    }
}
/**
 * 创建一个单向的环形链表
 */
class CircleSingleLinkedList {
    /**
     * 创建first节点
     */
    private Boy first = new Boy(-1);
    /**
     * 添加节点,构成环形链表
     */
    public void addBoy(int nums) {
        //数据判断
        if (nums < 1) {
            System.out.println("nums值需要大于1");
            return;
        }
        //临时变量
        Boy curBoy = null;
        //使用for创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号,创建节点
            Boy boy = new Boy(i);
            //第一个小孩节点
            if (i == 1) {
                first = boy;
                //形成环形
                first.setNext(first);
                //curBoy 指向第一个小孩节点
                curBoy = first;
            } else {
                //指向新建的节点
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    /**
     * 遍历当前的环形链表
     */
    public void showBoy() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("链表为空!!");
            return;
        }
        //first 节点不能移动,创建临时指针
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号:%d\n", curBoy.getNo());
            //遍历结束
            if (curBoy.getNext() == first) {
                break;
            }
            //curBoy后移
            curBoy = curBoy.getNext();
        }
    }
    /**
     * 根据输入,计算出圈的顺序
     * @param startNo 开始的节点
     * @param countNum 数几下
     * @param nums 圈内总共有几个节点
     */
    public void countBoy(int startNo, int countNum, int nums) {
        //校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("输入的数字有误。请重新输入");
            return;
        }
        //临时指针
        Boy helper = first;
        while (true) {
            //遍历借结束
            if (helper.getNext() == first) {
                break;
            }
            //helper后移
            helper = helper.getNext();
        }
        //报数前,先让 first 和 helper 移动 k - 1 次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //报数时,让first 和 helper 指针同时移动 m - 1 次,循环操作,直到圈中只有一个人
        while (true) {
            //判断圈中只有一个人
            if (helper == first) {
                System.out.println("最后一个人了");
                break;
            }
            //让first 和 helper 指针同时移动 countNum - 1 ,出圈
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //first指向出圈的节点
            System.out.printf("小孩 %d 出圈\n", first.getNo());
            //first指向出圈小孩的节点
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后圈中的小孩的编号是%d", helper.getNo());
    }
}
/**
 * 创建一个Boy类,表示一个节点
 */
class Boy {
    /**
     * 编号
     */
    private int no;
    /**
     * 下一个节点
     */
    private Boy next;
    public Boy(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}


栈 stack


先入后出的有序列表

栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一 种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另 一端为固定的一端,称为栈底(Bottom)

最先放入栈中元素在栈底,最后放入的元素在栈顶,而 删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除

出栈(pop) 、入栈(push)结构

应用场景


子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到 子程序执行完后再将地址取出,以回到原来的程序中

处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外, 也将参数、区域变量等数据存入堆栈中

表达式的转换 [ 中缀表达式转后缀表达式 ] 与求值(实际解决)

二叉树的遍历

图形的深度优先( depth一first )搜索法

栈的快速入门

  1. 用数组模拟栈
  2. 栈顶:定义变量初始值 top = -1
  3. 入栈:top++,stack[top] = data
  4. 出栈:int value = stack[top] ,top – ,return value
package com.stack;
import java.util.Scanner;
/**
 * 栈
 * @author Kcs 2022/8/11
 */
public class ArrayStackDemo {
    public static void main(String[] args) {
        //测试
        ArrayStack stack = 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":
                    stack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数字:");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.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("程序退出,欢迎下次再来!!!");
    }
}
/**
 * 定义一个ArrayStack 表示栈
 */
class ArrayStack {
    /**
     * 栈的的大小
     */
    private int maxSize;
    /**
     * 数组模拟栈
     */
    private int[] stack;
    /**
     * 初始化栈顶
     */
    private int top = -1;
    /**
     * 构造方法
     */
    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("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }
    /**
     * 出栈
     */
    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]);
        }
    }
}


栈实现综合案例-计算器

思路分析 (使用中缀表达式)

计算式:7 * 2 * 2 - 5 + 1- 5 * 3 - 3


首先创建两个栈

数栈(numStack):存放数

符号栈(operStack):存放运算符

通过一个index 值,来遍历表达式

扫描到一个数字,就直接加入数栈

扫描到一个运算符,则有两种情况

若当前符号栈为空,就直接入栈

若符号栈不为空,就进行比较,如果当前的操作符的优先级 小于 或 等于 栈中的操作符,则从数栈中pop数两个数,再从符号栈中pop出一个符号,进行运算,将其结果进入数栈,将当前的操作符入符号栈

如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈

当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并运行

最后在数栈只有一个数字,既是结果

处理多位数问题

不能发现一个数就立即入栈,可能是多位数

处理数式,需要项expression的表达式的index,后看一位,若是数九进行扫描,若是符号才入栈

定义一个字符串变量,进行拼接

package com.stack;
/**
 * @author Kcs 2022/8/12
 */
public class Calculator {
    public static void main(String[] args) {
        //扫描表达式
        String expression = "5456*2+5";
        //创建两个栈,数栈,符号栈
        ArrayCalStack numStack = new ArrayCalStack(10);
        ArrayCalStack operStack = new ArrayCalStack(10);
        //扫描变量
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        //用于每次扫描得到的char保存到ch
        char ch = ' ';
        //用于拼接多位数
        String keyNum = "";
        //循环扫描
        while (true) {
            //依次得到每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断是否为符号
            if (operStack.isOper(ch)) {
                //判断符号栈是否为空
                if (!operStack.isEmpty()) {
                    //如果当前的操作符的优先级 小于 或 等于 栈中的操作符,则从数栈中pop数两个数,再从符号栈中pop出一个符号,进行运算,
                    //将其结果进入数栈,将当前的操作符入符号栈
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        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 {
                //如果是数字就直接入数栈(存在多位数问题)
                //处理多位数
                keyNum += ch;
                //如果ch为expression最后的一位
                if (index == expression.length()-1){
                    numStack.push(Integer.parseInt(keyNum));
                }else {
                    //判断下一位是否为数字,若为数字,则进行扫描,若是运算符,则入符号栈
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))){
                        //如果后一位为运算符则入栈,keepNum ="112"
                        numStack.push(Integer.parseInt(keyNum));
                        //清空keepNum
                        keyNum = "";
                    }
                }
            }
            //让index + 1 ,判断是否扫描到最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        //当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并运行
        while (true) {
            //若符号栈为空,则计算最后的结果,数栈中只有一个数字
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            //运算结果入数栈
            numStack.push(res);
        }
        //将数栈最后的结果pop
        int result = numStack.pop();
        System.out.printf("表达式%s = %d", expression, result);
    }
}
/**
 * ArrayCalStack
 */
class ArrayCalStack {
    /**
     * 栈的的大小
     */
    private int maxSize;
    /**
     * 数组模拟栈
     */
    private int[] stack;
    /**
     * 初始化栈顶
     */
    private int top = -1;
    /**
     * 构造方法
     */
    public ArrayCalStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    /**
     * 返回当前栈顶的值,但并不pop
     */
    public int peek() {
        return stack[top];
    }
    /**
     * 栈满
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }
    /**
     * 栈空
     */
    public boolean isEmpty() {
        return top == -1;
    }
    /**
     * 入栈
     */
    public void push(int value) {
        //判断是否栈满
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }
    /**
     * 出栈
     */
    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 priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            //只有 + - * /
            return -1;
        }
    }
    /**
     * 判断是否是一个优先级
     */
    public boolean isOper(char var) {
        return var == '+' || var == '-' || var == '*' || var == '/';
    }
    /**
     * 计算方法
     */
    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;
            default:
                break;
        }
        return res;
    }
}

前缀(波兰表达式)

  • 前缀表达式的运算符位于操作数之前

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

计算机求职

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个 数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上 述过程直到表达式最左端,最后运算得出的值即为表达式的结果

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 的表达式的求值步骤


从右至左扫描,将6、5、4、3压入堆栈

遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7, 再将7入栈

接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈

最后是-运算符,计算出35-6的值,即29,由此得出最终结果


中缀

  • 最常见的运算规则

后缀

  • 运算符位于操作数之后

(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

计算规则


从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个 数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上 述过程直到表达式最右端,最后运算得出的值即为表达式的结果


从左至右扫描,将3和4压入堆栈;

遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入 栈;

将5入栈;

接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;

将6入栈;

最后是-运算符,计算出35-6的值,即29,由此得出最终结果


逆波兰计算器

  1. 输入一个逆波兰表达式(后缀表达式)使用栈(Stack)计算其结果
  2. 支持小括号和多位数,只对整数计算


分析
  1. 定义一个逆波兰表达式
  2. 依次将逆波兰表达式的数据和运算符存入到ArrayList中
  3. ArrayList 传递给一个方法,遍历ArrayList,配合栈,完成计算
package com.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * @author Kcs 2022/8/13
 */
public class PolandNotation {
    public static void main(String[] args) {
        //定义一个逆波兰表达式 (3+4)×5-6 ,4 5 * 8 - 60 + 8 2 / +,存在空格符号
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        //将ArrayList传递给一个方法,遍历
        List<String> list = getListString(suffixExpression);
        System.out.println("list=" + list);
        int res = calculate(list);
        System.out.println("result = " + res);
    }
    /**
     * 表达式 存入ArrayList中
     * @param suffixExpression
     * @return String[]
     */
    public static List<String> getListString(String suffixExpression) {
        //将表达式分割
        String[] spilt = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : spilt) {
            list.add(ele);
        }
        return list;
    }
    // 逆波兰表达式的运算
    public static int calculate(List<String> ls) {
        //创建给栈,只需要一个栈
        Stack<String> stack = new Stack<String>();
        // 遍历 ls
        for (String item : ls) {
            //判断是否位数,正则表达式
            //匹配多位数
            if (item.matches("\\d+")) {
                //入栈
                stack.push(item);
            } else {
                //pop出两个数,并运算,再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                //判断前的符号
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    //用后出栈的减去先出栈的
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    //用后出栈的 除以 先出栈的
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有问题,不属于四则运算符号");
                }
                stack.push("" + res);
            }
        }
        //最后留在栈里的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}


中缀转后缀

将这个中缀表达式:1 + (( 2 + 3) × 4 ) - 5 ===》后缀表达式

分析步骤

初始化两个栈:运算符栈 s1 和 储存中间 结果的栈 s2;

从左至右扫描中缀表达式;

遇到操作数时,将其压s2;

遇到运算符时,比较其与s1栈顶运算符的优先级:

如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

否则,若优先级比栈顶运算符的高,也将运算符压入s1;

否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4.1)与s1中新的栈顶运算 符相比较;

遇到括号时:

如果是左括号 “(” ,则直接压入s1

如果是右括号 “)” ,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃

重复步骤2至5,直到表达式的最右边

将s1中剩余的运算符依次弹出并压入s2

依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式。

package com.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * @author Kcs 2022/8/13
 */
public class PolandNotation {
    public static void main(String[] args) {
        // 中缀 ===》后缀
        // 1 + (( 2 + 3) * 4 ) - 5 ===》1 2 3 + 4 * + 5 –
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("中缀表达式:" + infixExpressionList);
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        System.out.println("后缀表达式:" + suffixExpressionList);
        System.out.println("后缀表达式的结果 = " + calculate(suffixExpressionList));
    /**
     * 将中缀表达式转为List 上面的中缀表达式存入List得到的结果:[1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5]
     */
    public static List<String> toInfixExpressionList(String s) {
        //存放中缀表达式内容
        ArrayList<String> list = new ArrayList<>();
        //定义指针,遍历中缀表达式
        int i = 0;
        //多位拼接
        String str;
        char c;
        do {
            //c为非数字
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                //后移
                i++;
            } else {
                //多位数
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }
    /**
     * 将得到的中缀表达式转换成 后缀表达式
     */
    public static List<String> parseSuffixExpressionList(List<String> list) {
        // 定义栈 符号栈
        Stack<String> s1 = new Stack<String>();
        //存储中间结果的栈,使用List方便操作
        List<String> s2 = new ArrayList<String>();
        //遍历list
        for (String item : list) {
            //为数,入s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                //将左括号弹出,消除小括号
                s1.pop();
            } else {
                //item的优先级比s1栈顶的优先级小,将s1栈顶的运算符弹出并压入到s2中,再次转到与s1中新的栈顶运算符相比较
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //将item 压入栈顶
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        //存放到list,正常输入就是逆波兰表达式
        return s2;
    }
    /**
     * 表达式 存入ArrayList中
     * @param suffixExpression
     * @return String[]
     */
    public static List<String> getListString(String suffixExpression) {
        //将表达式分割
        String[] spilt = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : spilt) {
            list.add(ele);
        }
        return list;
    }
    // 逆波兰表达式的运算
    public static int calculate(List<String> ls) {
        //创建给栈,只需要一个栈
        Stack<String> stack = new Stack<String>();
        // 遍历 ls
        for (String item : ls) {
            //判断是否位数,正则表达式
            //匹配多位数
            if (item.matches("\\d+")) {
                //入栈
                stack.push(item);
            } else {
                //pop出两个数,并运算,再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                //判断前的符号
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    //用后出栈的减去先出栈的
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    //用后出栈的 除以 先出栈的
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有问题,不属于四则运算符号");
                }
                stack.push("" + res);
            }
        }
        //最后留在栈里的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}
/**
 * 优先级高低,返回运算符对应的优先级
 */
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;
    }
}
目录
相关文章
|
13天前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
26天前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
27天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
68 16
|
30天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
|
30天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
62 6
|
1月前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
1月前
|
存储 监控 算法
探秘局域网桌面监控:深入剖析 Java 语言核心算法
在数字化办公时代,局域网桌面监控如同企业的“智慧鹰眼”,确保工作效率与数据安全。本文以Java为载体,揭示哈希表在监控中的关键应用。通过高效的数据结构和算法,哈希表能快速索引设备连接信息,大幅提升监控的时效性和响应速度。代码示例展示了如何用Java实现设备网络连接监控,结合未来技术如AI、大数据,展望更智能的监控体系,助力企业在数字化浪潮中稳健前行。
|
1月前
|
运维 监控 算法
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
65 32
|
2月前
|
监控 算法 网络协议
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
84 15
|
2月前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
52 6

热门文章

最新文章

  • 1
    局域网屏幕监控系统中的Python数据结构与算法实现
    132
  • 2
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    48
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    45
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    50
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    53
  • 6
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    39
  • 7
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    71
  • 8
    2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    37
  • 9
    2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    46
  • 10
    2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    44