算法面经--栈

栈

一、栈的实际需求

1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以

回到原来的程序中。

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

栈中。

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

请输入一个表达式

计算式:[722-5+1-5+3-3] 点击计算【如下图】

栈1.png

4. 二叉树的遍历。

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

二、栈的基本介绍

1. 栈的英文为(stack)

2) 栈是一个先入后出**(FILO-First In Last Out)的有序列表。

3. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的

一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

**4) 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元

素最先删除，最先放入的元素最后删除

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

栈2.png 栈3.png

三、实际操作实现

栈4.png

3.1 实现 栈的 思路分析

1. 使用数组来模拟栈

2. 定义一个 top 来表示栈顶，初始化 为 -1

3. 入栈的操作，当有数据加入到栈时， top++; stack[top] = data;

4. 出栈的操作， int value = stack[top]; top--, return value

3.2 案例实现

案例描述：使用栈完成计算 一个表达式的结果 722-5+1-5+3-4 = ？ 3+2*6-2

栈5.png

使用栈完成表达式的计算 思路

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

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

3. 如果发现扫描到是一个符号, 就分如下情况 3.1 如果发现当前的符号栈为 空，就直接入栈 3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.

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

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

代码实现：

package stack;
​
public class Calculator {
​
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 //完成表达式的运算
 String expression = "7*2*2-5+1-5+3-4"; // 15//如何处理多位数的问题？
 //创建两个栈，一个数栈，一个符号栈
 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
 String keepNum = ""; //用于拼接，多位数
 //开始while循环的扫描expression
 while(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(ch);
 //将当前的操作符入符号栈
 operStack.push(ch);
 }else{
 //如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
 operStack.push(ch);
 }
 }else{
 //如果为空直接入符号栈
 operStack.push(ch);
 }
 }else{
 //如果是数，则直接入数栈
 //numStack.push(ch - 48); //? "1+3" '1' => 1
 //分析思路
 //1\. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
 //2\. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
 //3\. 因此我们需要定义一个变量 字符串，用于拼接

 //处理多位数
 keepNum += ch;

 //如果ch已经是expressionde 最后一位，就直接入栈
 if(index == expression.length() - 1){
 numStack.push(Integer.parseInt(keepNum));
 }else{
 //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
 //注意是看后一位，不是index++
 if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))){
 //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
 numStack.push(Integer.parseInt(keepNum));
 //重要的!!!!!!, keepNum清空
 keepNum = "";
 }
 }
 }
 //让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);
 }
​
}
​
// 先创建一个栈,直接使用前面创建好
// 定义一个 ArrayStack2 表示栈, 需要扩展功能
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];
 }
​
 // 增加一个方法，可以返回当前栈顶的值, 但是不是真正的pop
 public 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]);
 }
 }// list()
 // 返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
 // 数字越大，则优先级就越高.
​
 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) { // oper表示运算符
 int res = 0;
 switch (oper) {
 case '+':
 res = num1 + num2;
 break;
​
 case '-':
 res = num2 - num1; // 顺序num2 - num1
 break;
 case '*':
 res = num1 * num2;
 break;
 case '/':
 res = num2 / num1;
 break;
 default:
 break;
 }
 return res;
 }
}
​

3.3 案例实现 带括号的表达式求值--（逆波兰 【后缀】表达式求值）

<u style="box-sizing: border-box;">知识点跳转说明：</u>此段diamante内容需要提前了解 前、中、后表达式的规则及转换。**

3.3.1 案例说明

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

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

例子： (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，由此得出最终结果

实现代码：

 package com.atguigu.stack;
 ​
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Stack;
 ​
 public class PolandNotation {
 ​
  public static void main(String[] args) {

  //完成将一个中缀表达式转成后缀表达式的功能
  //说明
  //1\. 1+((2+3)×4)-5 => 转成  1 2 3 + 4 × + 5 –
  //2\. 因为直接对str 进行操作，不方便，因此 先将  "1+((2+3)×4)-5" =》 中缀的表达式对应的List
  //   即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
  //3\. 将得到的中缀表达式对应的List => 后缀表达式对应的List
  //   即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]

  String expression = "1+((2+3)*4)-5";//注意表达式 
  List<String> infixExpressionList = toInfixExpressionList(expression);
  System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
  List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
  System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] 

  System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?

  /*

  //先定义给逆波兰表达式
  //(30+4)×5-6  => 30 4 + 5 × 6 - => 164
  // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + 
  //测试 
  //说明为了方便，逆波兰表达式 的数字和符号使用空格隔开
  //String suffixExpression = "30 4 + 5 * 6 -";
  String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
  //思路
  //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);

  */
  }

  //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
  //方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
  public static List<String> parseSuffixExpreesionList(List<String> ls) {
  //定义两个栈
  Stack<String> s1 = new Stack<String>(); // 符号栈
  //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
  //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
  //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
  List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2

  //遍历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();//!!! 将 ( 弹出 s1栈， 消除小括号
  } else {
  //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与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());
  }
 ​
  return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List

  }

  //方法：将 中缀表达式转成对应的List
  //  s="1+((2+3)×4)-5";
  public static List<String> toInfixExpressionList(String s) {
  //定义一个List,存放中缀表达式 对应的内容
  List<String> ls = new ArrayList<String>();
  int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
  String str; // 对多位数的拼接
  char c; // 每遍历到一个字符，就放入到c
  do {
  //如果c是一个非数字，我需要加入到ls
  if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
  ls.add("" + c);
  i++; //i需要后移
  } else { //如果是一个数，需要考虑多位数
  str = ""; //先将str 置成"" '0'[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;//返回
  }

  //将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
  public static List<String> getListString(String suffixExpression) {
  //将 suffixExpression 分割
  String[] split = suffixExpression.split(" ");
  List<String> list = new ArrayList<String>();
  for(String ele: split) {
  list.add(ele);
  }
  return list;

  }

  //完成对逆波兰表达式的运算
  /*
  * 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 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("运算符有误");
  }
  //把res 入栈
  stack.push("" + res);
  }

  }
  //最后留在stack中的数据是运算结果
  return Integer.parseInt(stack.pop());
  }
 ​
 }
 ​
 //编写一个类 Operation 可以返回一个运算符 对应的优先级
 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("不存在该运算符" + operation);
  break;
  }
  return result;
  }

 }