总结
双向链表在之前的基础上：
- 对比单向链表 双向链表可以自己删除，
- 双线链表正反遍历更加的容易
环形链表
认识单向环形链表
这里我们以单向环形链表为例子
就是我们最后一个节点的next域指向头结点，形成闭环
引用场景以及问题
Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由
此产生一个出队编号的序列。
思路提示：
提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。
Josephu 问题解题思路
认识约瑟夫问题，以及我们想要实现的场景，
- 编写实现 单向环形链表
- 约瑟夫问题的要求 根据区间报数 报数的小孩出列
- coding 出我们需要的需求
实现单向循环链表
思路
大体上和我们的单向链表有雷同的地方，区别在于：
- 我们需要在创建链表的时候将尾结点的最后一个指向头结点，这也就意味着我们需要有至少两个指针来记录头尾节点。
- 遍历的方式也要有些许的变化，结束循环的条件从
head.next = null改变成CurBoy.next(指向尾部节点的指针) = first;最后为头节点的时候遍历为第二个
我们简单的先创建一个实现链表需要的节点对象
约瑟夫问题环形链表的节点
//环形链表 约瑟夫问题 节点 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) { No = no; } public Boy getNext() { return Next; } public void setNext(Boy next) { Next = next; } }
创建环形链表对象实现生成链表和遍历链表，以及解决约瑟夫问题的方（具体的实现思路见代码注释）
// 环形单向链表 class CircleSingleLinkeList { Boy first = null; /** * @author 冷环渊 Doomwatcher * @context: 一个环形链表 参数是这个链表有多少节点 * @date: 2021/12/21 15:47 * @param nums * @return: void */ public void CreateListNode(int nums) { if (nums < 1) { System.out.println("无法开始游戏，因为链表小于最小的游戏节点数量"); return; } // 创建一个 辅助之间用于遍历和指向节点 Boy curBoy = null; for (int i = 1; i <= nums; i++) { Boy boy = new Boy(i); //如果只有一个节点的话 也可以生成环形链表 if (i == 1) { first = boy; first.setNext(first); curBoy = first;//将辅助指针指向链表的第一个节点 形成闭环 } else { // 如果不是一个的话就生成多个节点 curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } public void showListBoy() { if (first == null) { System.out.println("链表为空，不能遍历"); return; } // frist 节点不能移动 我们创建一个指针 Boy curboy = first; while (true) { System.out.printf("小孩的编号是： %d \n", curboy.getNo()); // 说明已经遍历完毕 if (curboy.getNext() == first) { break; } //后移 curboy curboy = curboy.getNext(); } } /** * @author 冷环渊 Doomwatcher * @context: 这里我们以小孩做游戏来解决约瑟夫问题， * @date: 2021/12/22 21:16 * @param nums 一共有多少个小孩 * @param start 从那个小孩开始报数 * @param index 每隔几个小孩报数一次 * @return: void */ public void JosephuFunc(int nums, int start, int index) { if (first == null || start < 1 || start > nums) { System.out.println("参数不对，请重新输入参数"); return; } Boy helper = first; //将 helper遍历到最后一个节点 while (true) { if (helper.getNext() == first) { break; } helper = helper.getNext(); } // 小孩子 报数之前，要遍历指针到从start开始的小孩的节点 for (int i = 0; i < start - 1; i++) { first = first.getNext(); helper = helper.getNext(); } //当小孩报数的时候 让 first和helper 同时移动m-1次 然后出圈 //这里循环操作 知道圈中的一个节点 while (true) { //说明列表只有一个节点 if (helper == first) { break; } //循环之后将 指针后移 for (int i = 0; i < index - 1; i++) { first = first.getNext(); helper = helper.getNext(); } // 这个时候 first选中的节点就是要出圈的小孩 System.out.printf("小孩 %d 出圈\n", first.getNo()); //出圈操作 first = first.getNext(); helper.setNext(first); } System.out.printf("最后剩下的小孩 %d \n", first.getNo()); } }
实现结果
栈
我们这里将一个场景带入学习
请输入一个表达式
计算式:[722-5+1-5+3-3] 点击计算 计算出结果
请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 2 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。----> 栈
栈的介绍
- 栈的英文为(stack)
- 栈是一个先入后出(FILO-First In Last Out)的有序列表。
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的 一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
- 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元 素最先删除，最先放入的元素最后删除
- 图解方式说明出栈(pop)和入栈(push)的概念
入栈与出栈 ： 栈 数据结构的特性 先入后出
栈的应用场景
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以 回到原来的程序中。
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆 栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。
- 图形的深度优先(depth 一 first)搜索法。
栈 快速入门（数组模拟栈）
实现思路
详细的每一部分的思路 都在代码的注释当中，想要详细理解可以参考代码中的注释
package com.hyc.DataStructure.Stack; import java.util.Scanner; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: ArrayStackDemo * @author: 冷环渊 doomwatcher * @description: TODO 用数组来模拟栈 * @date: 2021/12/23 18:08 * @version: 1.0 */ public class ArrayStackDemo { public static void main(String[] args) { //测试一下 ArrayStack 是否正确 //先创建一个 ArrayStack 对象->表示栈 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("exit: 退出程序"); System.out.println("push: 表示添加数据到栈(入栈)"); System.out.println("pop: 表示从栈取出数据(出栈)"); 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("程序退出~~~"); } } class ArrayStack { //栈的最大长度 private int MaxSize; //模拟栈 数据就放在这个数组里 private int[] stack; // 等于栈顶 默认等于-1 代表最底部分 private int top = -1; public ArrayStack() { } // 初始化栈 public ArrayStack(int maxSize) { MaxSize = maxSize; stack = new int[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 data) { if (isFull()) { System.out.println("栈满"); return; } top++; stack[top] = data; } // 将数据取出栈 public int pop() { if (isempty()) { throw new RuntimeException("栈是空的 无法取出"); } int value = stack[top]; top--; return value; } //遍历栈 遍历的时候需要从栈顶开始显示数据 public void list() { if (isempty()) { System.out.println("栈是空的"); } // 从栈顶开始输出 其实就是倒序的输出数组 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } }
小总结
- 这里我们用数组模拟了栈的一些基础操作，入栈出栈遍历内容，
- 除了使用数组，我们还可以使用链表来实现栈，这里我也写了这种写法有详细的注释，代码如下
package com.hyc.DataStructure.Stack; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: ListStackDemo * @author: 冷环渊 doomwatcher * @description: TODO 用链表来模拟栈 * @date: 2021/12/23 18:23 * @version: 1.0 */ public class ListStackDemo { public static void main(String[] args) { listStack listStack = new listStack(); listStack.push(5); listStack.push(6); listStack.push(9); System.out.println("出栈前"); listStack.list(); System.out.println("出栈后"); System.out.println("出栈：" + listStack.pop()); System.out.println("出栈：" + listStack.pop()); listStack.list(); } } class listStack { //创建一个头结点 StackNode head = new StackNode(0); StackNode temp = head; //判断是否为空 public boolean isempty() { return head.next == null; } //压入栈 public void push(int value) { //创建节点对象 StackNode newnode = new StackNode(value); //改变头节点指针的指向 temp.next = newnode; //指针后移 temp = temp.next; } //出栈 public int pop() { if (isempty()) { throw new RuntimeException("栈空"); } StackNode Before = head; //将 before 节点遍历到 temp也就是最后一个节点的上一个节点，让temp指针想前遍历 while (true) { if (Before.next == temp) { break; } Before = Before.next; } //将before的下一个节点为空相当于出栈之后 删除引用 Before.next = null; //取值 int value = temp.data; //此时 before指向的这个节点就是上一个节点的位置，将temp前移动，重复操作实现出栈 temp = Before; return value; } //遍历栈 public void list() { // 判断非空 if (isempty()) { System.out.println("栈是空的"); return; } StackNode temp = head; while (true) { if (temp.next == null) { break; } System.out.println(temp.next.data); temp = temp.next; } } } //单向链表节点 class StackNode { // 数据 public int data; //下一个节点 public StackNode next; public StackNode(int data) { this.data = data; } //方便输出语句输出 @Override public String toString() { return "StackNode{" + ", data='" + data + '\'' + ", next=" + next + '}'; } }
中缀表达式计算器
使用栈来实现综合计算器
计算机底层是如何处理这种公式的呢，思路如下
我们需要使用两个栈，一个记录数字，一个记录符号，根据这个栈的数据特性来通过符号和数据的出现规则来实现公式的计算
思路
- 1.通过一个index值（素引）,来遍历我们的表达式
- 2.如果我们发现是一个数字，就直接入数栈
- 3.如果发现扫描到是一个符号，就分如下情况
- 3.1如果发现当前的符号栈为空，就直接入栈
- 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
- 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
- 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
- 于栈中的操作符，就直接入符号找。
- 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
- 5.最后在数栈只有一个数字，就是表达式的结果
- 验证：3+2*6-2=13
- 这里我们就根据上面的思路实现接下来的思路
代码实现
package com.hyc.DataStructure.Stack; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: Calculator * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/24 20:39 * @version: 1.0 */ public class Calculator { public static void main(String[] args) { // 根据文章的思路 我们这里完成对一串计算只包含加减乘除的表达式运算操作 String expression = "3+2*6-2"; /** 计算思路 使用栈完成表达式的计算思路 * 1.通过一个index值（素引）,来遍历我们的表达式 * 2.如果我们发现是一个数字，就直接入数栈 * 3.如果发现扫描到是一个符号，就分如下情况 * 3.1如果发现当前的符号栈为空，就直接入栈 * 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中 * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算， * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大 * 于栈中的操作符，就直接入符号找。 * 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行. * 5.最后在数栈只有一个数字，就是表达式的结果 * 验证：3+2*6-2=13 * 这里我们就根据上面的思路实现接下来的思路 * */ // 创建两个栈 一个存放需要计算的数字 一个存放需要运算的符号 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 keepNums = ""; //开始while 循环扫描表达式 expression while (true) { // 一次得到expression的每一个字符 ch = expression.substring(index, index + 1).charAt(0); // 判断ch 是什么（数字或者符号）之后进行操作 if (operStack.isOper(ch)) { /* 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中 * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算， * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大 * 于栈中的操作符，就直接入符号找。*/ //非空判断 if (!operStack.isempty()) { if (operStack.priotrity(ch) <= operStack.priotrity(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 { // 如果是数字 就直接进入数字栈 /*思路 * 这里我们要考虑到多位数 在处理多位数的时候 * 我们需要扫描这个数的下一位一直到找到下一个符号 * 这个时候我们定义一个字符串用于拼接找到的数 * */ // 处理多位数 keepNums += ch; // 如果ch已经是 expression 最后一位name就直接入栈 if (index == expression.length() - 1) { numStack.push(Integer.parseInt(keepNums)); } else { // 判断下一个字符是不是数字 ，如果是就继续向下判断 是运算符则入栈，这里我们要看的是结束的地方是不是符号 if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { //如果最后一位事原酸父则如入栈 这里我们的操作变化就是 keepnums =1 或者是 keepnums = 123 numStack.push(Integer.parseInt(keepNums)); // 加入之后能讲 keepnunms清空 用于下一位的判断 keepNums = ""; } } } // 让 index +1 并判断是否扫描到expression 最后 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 res2 = numStack.pop(); System.out.printf("表达式%s = %d", expression, res2); } } /* * 应为要实现计算器 我们需要编写一些新的功能， * */ class ArrayCalStack { //栈的最大长度 private int MaxSize; //模拟栈 数据就放在这个数组里 private int[] stack; // 等于栈顶 默认等于-1 代表最底部分 private int top = -1; public ArrayCalStack() { } // 初始化栈 public ArrayCalStack(int maxSize) { MaxSize = maxSize; stack = new int[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 data) { if (isFull()) { System.out.println("栈满"); return; } top++; stack[top] = data; } // 将数据取出栈 public int pop() { if (isempty()) { throw new RuntimeException("栈是空的 无法取出"); } int value = stack[top]; top--; return value; } //遍历栈 遍历的时候需要从栈顶开始显示数据 public void list() { if (isempty()) { System.out.println("栈是空的"); } // 从栈顶开始输出 其实就是倒序的输出数组 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } /* 返回运算符的优先级 这个规则我们可以自己来设定 优先级使用数字来表示 * 数字越大优先级约高 * */ public int priotrity(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 = num2 / num1; break; case '*': res = num1 * num2; break; default: break; } return res; } }
这里我们实现了基础的表达式运算，但是我们没有考虑的事
- 我们实现了基本计算，但是没有考虑小括号等
- 中缀表达式对我们来说是十分的好算的，但是对于计算机计算是不方便的，之后会给大家更新适合计算机计算的后缀表达式
中缀转后缀表达式 逆波兰计算器实现
什么是前缀，什么中缀，什么是后缀？（理论加举例）
前缀
前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
我们完成一个逆波兰计算器，要求完成如下任务:
- 输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
- 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
中缀
（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。
与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。
与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。
例：
（1）8+4-6*2用后缀表达式表示为：
8 4+6 2*-
（2）2*（3+5）+7/1-4用后缀表达式表示为：
235+*71/+4-
后缀
这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用械实现求值。对于表达式x:=(a+b)(c+d)，其后缀式为xab+cd+:=。
原表达式：a(b(c+d/e)-f)# / # 为表达式结束符号/
后缀式：abcde/+f-#
为运算符定义优先级：# ( + - * / **
-1 0 1 1 2 2 3
从原表达式求后缀式的规则为：
思路分析
例如: (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，由此得出最终结果
代码实现
public static void main(String[] args) { //定义逆波兰表达式 // 测试 String suffixExpression = "3 4 + 5 * 6 -"; // 思路 // 1. 先将 3 4 + 5 * 6 - 方法哦 ArrayList中 // 2. 将 Arraylist 传递一个方法 遍历ArrayList 配合栈完成计算 List<String> list = getListString(suffixExpression); System.out.println("rpnlist = " + list); int res = calculate(list); System.out.println("计算的结果是 = " + res); } /** * @author 冷环渊 Doomwatcher * @context: 将一个逆波兰表达式的数据和运算符 依次放入Arraylist中 * @date: 2021/12/25 18:09 * @param suffixExpression * @return: java.util.List<java.lang.String> 将分割好的字符List 返回 */ public static List<String> getListString(String suffixExpression) { // 分割字符串 将后缀表达式的每一个字符取出 String[] split = suffixExpression.split(" "); // 我们用list 来存储分割出来的表达式，这样之后我们就需要遍历即可 List<String> list = new ArrayList<>(); for (String ele : split) { list.add(ele); } return list; } /** * @author 冷环渊 Doomwatcher * @context: 这个方法就是 逆波兰表达式的运算处理方法 * * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 - * * 1） 从左至右扫描，将3和4压入栈 * * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈 * * 3） 将5 入栈 * * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5 = 35 将结果入栈 * * 5） 将6 入栈 * @date: 2021/12/25 18:14 * @param ls * @return: int 返回的是一个运算结果 */ public static int calculate(List<String> ls) { //创建栈 只需要一个栈即可 Stack<String> stack = new Stack<>(); // 遍历处理 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 ("+".equals(item)) { res = num1 + num2; } else if ("-".equals(item)) { res = num1 - num2; } else if ("*".equals(item)) { res = num1 * num2; } else if ("/".equals(item)) { res = num1 / num2; } else { throw new RuntimeException("运算符有误"); } // 把 res 入栈 stack.push("" + res); } } //最后留在stack 中的数据是运算结果 return Integer.parseInt(stack.pop()); }
这里我们用list加栈的方式实现了表达式的运算
需要注意的几点：
- 从中体会 后缀表达式和中缀表达式的转换
- 计算上，后缀与中缀的区别
中缀转后缀表达式
大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发 中，我们需要将 中缀表达式转成后缀表达式。 所以我们需要用代码将中缀表达式处理成后缀表达式之后运算一劳永逸
思路
1.初始化两个栈 元素安抚栈 s1 和存储中间结果的栈2
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 com.hyc.DataStructure.Stack; import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: PolandExpression * @author: 冷环渊 doomwatcher * @description: TODO * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 - * 1） 从左至右扫描，将3和4压入栈 * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈 * 3） 将5 入栈 * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5 = 35 将结果入栈 * 5） 将6 入栈 * 最后 是 - 运算符 计算出 35-6 = 29 由此得出最后的结果 * * 使用技术 这里我们用 java给我们提供的 Stack 和 ArrayList组合来实现计算器 * @date: 2021/12/25 18:00 * @version: 1.0 */ public class PolandExpression { public static void main(String[] args) { //定义中缀表达式 ，转成后置表达式之后运算 String expression = "1+((2+3)*4)-5"; //拆成链表 List<String> infixExpressionList = toinfixExpression(expression); System.out.println("中缀表达式对应的list=" + infixExpressionList); List<String> suffixexpression = parseSuffixExpressionList(infixExpressionList); System.out.println("后缀表达式对应的List" + suffixexpression); System.out.printf("expression=%d", calculate(suffixexpression)); //定义逆波兰表达式 // 测试 String suffixExpression = "3 4 + 5 * 6 -"; // 思路 // 1. 先将 3 4 + 5 * 6 - 方法哦 ArrayList中 // 2. 将 Arraylist 传递一个方法 遍历ArrayList 配合栈完成计算 List<String> list = getListString(suffixExpression); System.out.println("rpnlist = " + list); int res = calculate(list); System.out.println("计算的结果是 = " + res); } /** * @author 冷环渊 Doomwatcher * @context: 将 Arraylist[1,+,(,(,2,+,3,),*,4,),-,5] 转化成 Arraylist[1,2,3,+,4,*,5,-] * 转换思路： * 1. 初始化两个栈 元素安抚栈 s1 和存储中间结果的栈2 * 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中的元素并且输出，结果逆序就是中缀表达式对应的后缀的表达式 * * @date: 2021/12/27 17:48 * @param * @return: java.util.List<java.lang.String> */ public static List<String> parseSuffixExpressionList(List<String> ls) { // 定义两个栈 /*符号栈*/ Stack<String> s1 = new Stack<>(); /* S2 思路说明 * 这里我们使用栈 在转换过程中我们不需要pop操作，而且这个s2 之后我们需要逆序输出操作很麻烦 * 于是这里使用List来当作 s2 的数据存储结构 * */ List<String> s2 = new ArrayList<>(); // 遍历 ls for (String item : ls) { // 如果是一个数字 那么就加入 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()); } // 之后将 itea 压入栈 s1.push(item); } } // 将s1中剩余的运算符一次弹出加入s2 while (s1.size() != 0) { s2.add(s1.pop()); } // 注意应为存放的是list 这里我们顺序不需要改变 直接输出就是对应的后缀表达式 return s2; } /** * @author 冷环渊 Doomwatcher * @context: 将中缀表达式 转换成对应的list * @date: 2021/12/27 17:32 * @param s * @return: java.util.List<java.lang.String> */ public static List<String> toinfixExpression(String s) { /*定义一个List 存放中缀表达式的对应内容*/ List<String> ls = new ArrayList<>(); //定义一个指针 用于遍历 中缀表达式的字符串 int i = 0; // 用于拼接字符串 String str; //用于存放遍历的字符 char c; do { // 如果c是一个非数字 那么我们需要加入到 ls 中去 ，这里的判断条件是 ASCLL值 if ((c = s.charAt(i)) < 48 || ((c = s.charAt(i)) > 57)) { ls.add("" + c); // 指针后移 i++; } else { /* * 如果是一个数字 那么我们还需要考虑是不是多位数 * 这里我们将 str 置空 * */ str = ""; 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; } /** * @author 冷环渊 Doomwatcher * @context: 将一个逆波兰表达式的数据和运算符 依次放入Arraylist中 * @date: 2021/12/25 18:09 * @param suffixExpression * @return: java.util.List<java.lang.String> 将分割好的字符List 返回 */ public static List<String> getListString(String suffixExpression) { // 分割字符串 将后缀表达式的每一个字符取出 String[] split = suffixExpression.split(" "); // 我们用list 来存储分割出来的表达式，这样之后我们就需要遍历即可 List<String> list = new ArrayList<>(); for (String ele : split) { list.add(ele); } return list; } /** * @author 冷环渊 Doomwatcher * @context: 这个方法就是 逆波兰表达式的运算处理方法 * * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 - * * 1） 从左至右扫描，将3和4压入栈 * * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈 * * 3） 将5 入栈 * * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5 = 35 将结果入栈 * * 5） 将6 入栈 * @date: 2021/12/25 18:14 * @param ls * @return: int 返回的是一个运算结果 */ public static int calculate(List<String> ls) { //创建栈 只需要一个栈即可 Stack<String> stack = new Stack<>(); // 遍历处理 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 ("+".equals(item)) { res = num1 + num2; } else if ("-".equals(item)) { res = num1 - num2; } else if ("*".equals(item)) { res = num1 * num2; } else if ("/".equals(item)) { res = num1 / num2; } else { throw new RuntimeException("运算符有误"); } // 把 res 入栈 stack.push("" + res); } } //最后留在stack 中的数据是运算结果 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; } }
总结
- 计算的思路和我们先前写的逆波兰计算器事一样的
- 这里我们考虑中缀转后缀的几个要点，运算符优先级和运算符的位置
- 动手之后，debug看看栈和List的变化加深理解
排序算法
快速排序
快速排序法介绍：
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两 部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序思路图：
快速排序的思路由上图所示：
- 首先是找到一个基准点，这个不一定非要是中位数，也可以是任意一位，可以自主分割，在什么位置都可以，这里我们以中位来学习
- 根据中位数为基准，将需要排序的数组分为两份，之后分别交换位置，保证比中位数小的都在左边，比中位数的都在右边，此时左右两边虽然无序，但是都保证一定规则
- 之后按照递归，再次将左边选出中位数，右边选出中位数，递归到不能交换为止
