栈Stack
1. 什么是栈
- 栈是一个先入后出的有序列表；
- 栈限制了元素的插入与删除只能在线性表的同一端进行（即栈顶Top），而另一端则为固定的一端（即栈底Bottom）。
2. 栈的常见应用场景
- 子程序调用
- 处理递归调用，ps：除了存地址还可以存参数和局部变量
- 表达式转换（中缀转后缀）与求值
- 二叉树遍历
- 图的深度优先搜索算法（DFS）
3. 数组模拟栈的思路与代码实现
3.1 思路分析
- 定义一个变量top表示栈顶，初始化为-1
- 当数据入栈时，top++，stack[top]=data
- 当数据出栈时，top--
3.2 代码实现
package com.datastructure;
import java.util.Scanner;
/**
* @author SnkrGao
* @create 2023-03-26 22:05
*/
public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
String key = " "; // 用于接收用户输入
boolean flag = true;
Scanner scanner = new Scanner(System.in);
while (flag) {
System.out.println("------------------------------------------");
System.out.println("测试数组模拟栈的使用说明：");
System.out.println("quit：退出程序");
System.out.println("push：向栈中插入数据");
System.out.println("pop：从栈顶取出数据");
System.out.println("ergodic：从栈顶遍历打印栈");
System.out.println("请输入你的选择：");
key = scanner.next();
switch (key) {
case "quit":
System.out.println("退出程序!");
flag = false;
scanner.close();
break;
case "ergodic":
arrayStack.ergodic();
break;
case "push":
System.out.println("请输入一个数：");
int data = scanner.nextInt();
arrayStack.push(data);
break;
case "pop":
try {
int result = arrayStack.pop();
System.out.println("当前出栈的栈顶数据是："+result);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
}
}
class ArrayStack {
private int MaxSize; // 栈的大小
private int[] stack;
private int top = -1; // 表示栈顶，初始化为-1
public ArrayStack(int maxSize) {
this.MaxSize = maxSize;
this.stack = new int[maxSize];
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == MaxSize -1;
}
// 入栈push
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 ergodic() {
if (isEmpty()) {
System.out.println("栈空！");
return;
}
for (int i = top; i >= 0 ; i--) {
System.out.println("stack["+i+"]="+stack[i]);
}
}
}
4. 栈实现综合计算器（中缀表达式）
4.1 思路：
- 创建一个index索引值，用于遍历表达式；
- 如果遍历到数字，就直接入数栈；
- 如果遍历到操作符，分如下情况讨论：
- 若符号栈为空，则直接入符号栈；
- 若符号栈不为空，则将当前符号与栈顶符号进行比较：
- 若当前operator的优先级大于栈顶的operator，则入栈；
- 若当前operator的优先级小于等于栈顶的operator，则从数栈中pop出两个数，并从符号栈中pop出一个运算符进行运算，将运算结果push进数栈，（
*注：此时需循环判断当前operator的优先级是否仍小于等于新的栈顶的优先级，若仍小于等于新的栈顶operator的优先级，重复执行上述步骤*eg.3-2*6-2）最后将当前operator入符号栈；
- 表达式遍历完毕，顺序地从数栈和符号栈取出数和运算符进行运算；
- 最终数栈中只剩一个数，即为表达式的计算结果。
4.2 代码实现
package com.datastructure;
/**
* @author SnkrGao
* @create 2023-03-29 13:31
*/
public class Calculator {
public static void main(String[] args) {
String expression = "12-2*2-2*3+1*3*2"; // 输入表达式
// 定义两个栈，分别为数栈和符号栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
int index = 0; // 用于遍历表达式
int num1, num2, operator, res= 0; // 用于计算
char ch = ' ';
String keepNum = ""; // 用于记录多位数字
while (index < expression.length()) {
// substring字符串提取，找到index索引对应位置的字符
ch = expression.substring(index, index+1).charAt(0);
// 判断当前符号是否为运算符
if (operStack.isOperator(ch)) {
// 判断符号栈是否为空，若为空直接入符号栈
if (!operStack.isEmpty()) {
// 符号栈不为空，循环判断当前运算符的优先级是否仍然小于等于栈顶的优先级
while (!operStack.isEmpty() && operStack.priority(ch) <= operStack.priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
operator = operStack.pop();
res = operStack.calculate(num1, num2, operator);
numStack.push(res);
}
operStack.push(ch);
}else {
operStack.push(ch);
}
}else { // 当前符号为数字，则直接入数字栈，但需考虑多位数字的情况
keepNum += ch;
// 如果当前字符已经是表达式的最后一位，即其一定是一个数，则直接入数栈
if (index == expression.length()-1) {
numStack.push(Integer.parseInt(keepNum));
}else {
// 查看后一位是否是运算符，若是，则将keepNum入数栈
// 若不是，则不做任何处理，index++后下一轮循环执行keepNum += ch
// 注意不能index++，而是继续用substring指定begin和end提取字符串
if (operStack.isOperator(expression.substring(index+1, index+2).charAt(0))) {
numStack.push(Integer.parseInt(keepNum));
// keepNum清空
keepNum = "";
}
}
}
index++;
}
// 表达式全部遍历完成，开始依序取出数栈和符号栈中的元素进行计算
// 判断条件应为：符号栈是否为空，当符号栈为空时，数栈只剩一个数即最终计算结果
while (!operStack.isEmpty()) {
num1 = numStack.pop();
num2 = numStack.pop();
operator = operStack.pop();
res = operStack.calculate(num1, num2, operator);
numStack.push(res);
}
int result = numStack.pop();
System.out.println("表达式"+expression+"="+result);
}
}
class ArrayStack2 {
private int MaxSize;
private int[] stack;
private int top = -1;
public ArrayStack2(int maxSize) {
this.MaxSize = maxSize;
this.stack = new int[maxSize];
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == MaxSize - 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 int peek() {
if (isEmpty()) {
throw new RuntimeException("栈空，无法显示栈顶元素！");
}
return stack[top];
}
public void ergodic() {
if (isEmpty()) {
System.out.println("栈空！");
return;
}
for (int i = top; i >= 0; i--) {
System.out.println("stack["+i+"]="+stack[i]);
}
}
// 判断当前遍历到的字符是否为一个运算符
public boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 返回运算符的优先级
public int priority(int operator) {
if (operator == '*' || operator == '/') return 1;
else if (operator == '+' || operator == '-') return 0;
else return -1;
}
// 计算
public int calculate(int num1, int num2, int operator) {
int res = 0;
switch (operator) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}