【数据结构(四)】栈（1）

---

1. 关于栈的一个实际应用

设计一个简单的计算器：
    输入一个表达式，点击计算得出结果。
如：计算式:[7 * 2 * 2 - 5 + 1 - 5 + 3 - 3] 点击计算【如下图】

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

2. 栈的介绍

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

图解方式说明出栈(pop)和入栈(push)的概念

3. 栈的应用场景

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

4. 栈的简单应用

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

4.1. 思路分析

思路分析：(使用数组来模拟栈)

①定义一个 top 来表示栈顶，初始化 为 -1
②入栈的操作，当有数据加入到栈时， top++; stack[top] = data;
③出栈的操作， int value = stack[top]; top--, return value

4.2. 代码实现

package stack;import java.util.Scanner;public class ArrayStackDemo {public static void main(String[] args) {// 创建一个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) {// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case "exit":scanner.close();loop = false;break;default:break;}}System.out.println("程序退出");}
}// 定义一个ArrayStck 表示栈
class ArrayStack {private int maxSize;// 栈的大小private int[] stack;// 数组，数组模拟栈：数据放在该数组private int top = -1;// 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;}// 入栈(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]);}}}

运行结果：

---

习题拓展：
将上面的程序改成使用链表来模拟栈。

---

5. 栈的进阶应用(实现综合计算器)

5.1. 栈实现一位数计算(中缀表达式)

使用栈来实现综合计算器

问题：
    请输入一个表达式，通过点击“点击计算”来输出计算结果
    计算的表达式为：7 * 2 * 2 - 5 + 1 - 5 + 3 - 3

5.1.1. 思路分析

假设：
计算表达式为：3 + 2 * 6 - 2

计算思路：

1.通过一个 index 值（索引），来遍历我们的表达式

2.如果我们发现是一个数字, 就直接入数栈

3.如果发现扫描到是一个符号, 就分如下情况

3.1. 如果发现当前的符号栈为 空，就直接入栈

3.2. 如果符号栈有操作符，就进行比较
（1）如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，；
（2）如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈。

因为计算表达式为：3 + 2 * 6 - 2
栈中已经存放了3和+，下一步该想数栈中存放2，直接入栈

接下来，扫描到符号 *
当前的操作符 * 的优先级大于栈中的操作符 + ，直接入符号栈

接下来，扫描到数字6，直接入数栈

接下来，扫描到符号 -
当前的操作符 - 的优先级小于(或等于)栈中的操作符 * ，直接入符号栈
需要从数栈中pop出两个数（6 和 2）,在从符号栈中pop出一个符号（*），进行运算，将得到结果（12），入数栈

2 * 6 = 12

然后将当前的操作符（ - ）入符号栈。

接下来，扫描到数字2，直接入数栈

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

①12 - 2 = 10

②3 + 10 =13

5.最后在数栈只有一个数字，就是表达式的结果（即13）

5.1.2. 代码实现

package stack;public class Calculator {public static void main(String[] args) {// 给出一个计算表达式String expression = "3+2*6-2";// String expression = "7+2*6-4";// 创建两个栈：数栈 和 符号栈ArrayStack2 numStack = new ArrayStack2(10);ArrayStack2 operStack = new ArrayStack2(10);// 定义相关变量int index = 0;// 用于扫描int num1 = 0;int num2 = 0;int oper = 0;int res = 0;char ch = ' ';// 将每次扫描得到的char保存到ch// 使用while循环的扫描expressionwhile (true) {// 一次得到expression的每一个字符ch = expression.substring(index, index + 1).charAt(0);// 判断ch是什么，然后做相应的处理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 {// 如果是数，直接入 数栈numStack.push(ch - 48);// ASCII码表对应数值要减去48}// 让index++，并判断是否扫描到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);}
}// 先创建一个栈
// 定义一个ArrayStck 表示栈
class ArrayStack2 {private int maxSize;// 栈的大小private int[] stack;// 数组，数组模拟栈：数据放在该数组private int top = -1;// top表示栈顶，初始化-1// 构造器public ArrayStack2(int maxSize) {this.maxSize = maxSize;stack = new int[this.maxSize];}// 增加一个方法，可以返回当前栈顶的值，但不是真正的poppublic int peek() {return stack[top];}// 栈满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 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 = num2 + num1;break;case '-':res = num2 - num1;break;case '*':res = num2 * num1;break;case '/':res = num2 / num1;break;default:break;}return res;}}

运行结果：

注意：
上述代码在计算多位数会出现问题（比如计算：30+2*6-2，会错误的计算成10）
因为在数据读取的时候，是一个字符一个字符的读取，这样就把30拆成了 3 和 0 ，因此计算出错。

5.2. 栈实现多位数计算(中缀表达式)

5.2.1. 解决思路

1.当处理多位数时，不能发现是一个数就立即入栈，因为它可能是多位数
2.在处理数时，需要向expression的表达式的index后再看一位，如果是多位数就进行扫描，如果是符号才入栈
3.因此我们需要定义一个变量 字符串，用于拼接

5.2.2. 代码实现：

package stack;public class Calculator {public static void main(String[] args) {// 给出一个计算表达式String expression = "30+2*6-2";// String expression = "7+2*6-4";// 创建两个栈：数栈 和 符号栈ArrayStack2 numStack = new ArrayStack2(10);ArrayStack2 operStack = new ArrayStack2(10);// 定义相关变量int index = 0;// 用于扫描int num1 = 0;int num2 = 0;int oper = 0;int res = 0;char ch = ' ';// 将每次扫描得到的char保存到chString keepNum = "";//用于拼接多位数// 使用while循环的扫描expressionwhile (true) {// 一次得到expression的每一个字符ch = expression.substring(index, index + 1).charAt(0);// 判断ch是什么，然后做相应的处理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 {// 如果是数，直接入 数栈// numStack.push(ch - 48);// ASCII码表对应数值要减去48//分析思路//1. 当处理多位数时，不能发现是一个数就立即入栈，因为它可能是多位数//2.在处理数时，需要向expression的表达式的index后再看一位，如果是多位数就进行扫描，如果是符号才入栈//3.因此我们需要定义一个变量 字符串，用于拼接//处理多位数keepNum += ch;//如果ch已经是expression的最后一位，就直接入栈if (index == expression.length() - 1) {numStack.push(Integer.parseInt(keepNum));} else {// 判断下一个字符是不是数字，如果是数字就继续扫描，如果是运算符，则入栈// 注意：这里是看后一位，不是index++if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {// 如果后一位是运算符，则入栈(keepNum可能是 一位数，也可能是 多位数)numStack.push(Integer.parseInt(keepNum));// 注意：一定要清空keepNumkeepNum = "";}}}// 让index++，并判断是否扫描到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);}
}// 先创建一个栈
// 定义一个ArrayStck 表示栈
class ArrayStack2 {private int maxSize;// 栈的大小private int[] stack;// 数组，数组模拟栈：数据放在该数组private int top = -1;// top表示栈顶，初始化-1// 构造器public ArrayStack2(int maxSize) {this.maxSize = maxSize;stack = new int[this.maxSize];}// 增加一个方法，可以返回当前栈顶的值，但不是真正的poppublic int peek() {return stack[top];}// 栈满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 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 = num2 + num1;break;case '-':res = num2 - num1;break;case '*':res = num2 * num1;break;case '/':res = num2 / num1;break;default:break;}return res;}}

运行结果：

---

习题拓展：

对上述代码加入功能，能够实现含小括号表达式的运算。