- 1、定义
- 2、应用场景
- 3、实现
- 3.1、用数组实现
- 4、应用
- 4.1、表达式求值
- 5、中缀转后缀
- 栈是一个先入后出的有序列表
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
- 最先放入的元素在栈底，且最后出栈。最后放入的元素在栈顶，且最先出栈
- 子程序递归调用。如JVM中的虚拟机栈
- 表达式转换（中缀转后缀）与求值
- 二叉树的遍历
- 图的深度优先遍历
思路
- 定义top表示栈顶，初始值为-1
- 入栈的操作，先让top++，再放入数组出
- 栈操作，先取出元素，在让top–
- top == -1时，栈空
- top == maxSize-1时，栈满
代码
public class Demo1 {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5);
//压栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
//出栈
System.out.println(stack.pop());
}
}
class ArrayStack {
private final int maxSize;
int[] stack;
private int top;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int [this.maxSize];
top = -1;
}
private boolean isEmpty() {
return top == -1;
}
private boolean isFull() {
return top == maxSize-1;
}
public void push(int i) {
if(isFull()) {
throw new StackOverflowError("栈满");
}
//压栈
top++;
stack[top] = i;
}
public int pop() {
if(isEmpty()) {
throw new EmptyStackException();
}
int retNum = stack[top];
top--;
return retNum;
}
}
4、应用
4.1、表达式求值
代码
存在的问题：因为栈是用的整型数组，所以计算除法的时候，无法转化成double
public class Demo2 {
public static void main(String[] args) {
String formula = "12+3*15+3/3";
//索引，用来读取字符串中的元素
int index = 0;
//保存读取到的数字和符号
int number1 = 0;
int number2 = 0;
int thisChar = ' ';
//用于拼接数字
StringBuilder spliceNumber = new StringBuilder();
//数栈和符号栈
ArrayStack2 numberStack = new ArrayStack2(10);
ArrayStack2 operationStack = new ArrayStack2(10);
//保存运算结果
int result;
//开始读取字符串中的元素
for (index = 0; index < formula.length(); index++) {
thisChar = formula.charAt(index);
if (operationStack.isOperation(thisChar)) {
if(operationStack.comparePriority(thisChar)) {
operationStack.push(thisChar);
} else {
int popChar = operationStack.pop();
number2 = numberStack.pop();
number1 = numberStack.pop();
//获得运算结果
result = operationStack.calculation(number1, number2, popChar);
operationStack.push(thisChar);
numberStack.push(result);
}
} else {
//如果是数字，就一直读取
while(thisChar>='0' && thisChar<='9') {
//可能该数字为多位数，所以不能只存入一位数字
spliceNumber.append(thisChar - '0');
System.out.println("拼接字符换 " + spliceNumber);
index++;
//如果已经读了最后一个数字了，就停下来
if(index >= formula.length()) {
break;
}
thisChar = formula.charAt(index);
}
int number = Integer.parseInt(spliceNumber.toString());
numberStack.push(number);
//初始化spliceNumber
spliceNumber = new StringBuilder();
index--;
}
}
while(!operationStack.isEmpty()) {
int popChar = operationStack.pop();
number2 = numberStack.pop();
number1 = numberStack.pop();
//获得运算结果
result = operationStack.calculation(number1, number2, popChar);
numberStack.push(result);
}
System.out.println(numberStack.pop());
}
}
class ArrayStack2 {
private final int maxSize;
int[] stack;
private int top;
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == maxSize - 1;
}
public void push(int i) {
if (isFull()) {
throw new StackOverflowError("栈满");
}
//压栈
top++;
stack[top] = i;
}
public int pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
int retNum = stack[top];
top--;
return retNum;
}
public void traverse() {
for(int thiChar : stack) {
System.out.println(thiChar);
}
}
public int getPriority(int operation) {
if (operation == '*' || operation == '/') {
return 2;
} else if (operation == '+' || operation == '-') {
return 1;
} else if (operation >= '0' && operation <= '9') {
return 0;
} else {
return -1;
}
}
public boolean comparePriority(int operation) {
if (isEmpty()) {
return true;
} else {
int priority1 = getPriority(operation);
int priority2 = getPriority(stack[top]);
return priority1 > priority2;
}
}
public boolean isOperation(int operation) {
return operation == '*' || operation == '/' || operation == '-' || operation == '+';
}
public int calculation(int number1, int number2, int operation) {
switch (operation) {
case '+':
return number1+number2;
case '-':
return number1-number2;
case '*':
return number1*number2;
case '/':
return number1/number2;
default:
System.out.println(operation);
throw new RuntimeException("符号读取错误！");
}
}
}
5、中缀转后缀
后缀表达式运算方法
- 从左向右读取表达式
- 遇到数字就压入栈中
- 遇到运算符就弹出栈顶和次顶元素。用次顶元素 运算符 栈顶元素，并将运算结果压入栈中，直到栈为空，最终结果就是运算结果
代码
public class Demo4 {
static Queue queue = new linkedList<>();
static Stack stack = new Stack<>();
public static void main(String[] args) {
//中缀表达式，加上空格，方便取出
String infixexpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
String[] expressionArr = infixexpression.split(" ");
//用来保存该运算符的类型
int type;
//取出的字符串
String element;
//弹出栈的字符串
String stackEle;
for(int i=0; i priority2) {
//该运算符优先级高于栈顶元素优先级，则入栈
stack.push(element);
}else {
stackEle = stack.pop();
queue.add(stackEle);
//重新判断该运算符
i--;
}
}
}
//把最后一个元素出栈并入队
stackEle = stack.pop();
queue.add(stackEle);
//保存队列长度，因为出队过程中队列的长度会被改变
int length = queue.size();
for(int i=0; i 
