栈(stack)的介绍
1.栈是一个先入后出(FILO-First In Last Out)的有序列表。
2.栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入
和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端称为栈底(Bottom)。
4，根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，
最后放入的元素最先删除，最先放入的元素最后删除。
5栈的插入操作(push)，称压栈、入栈。类似子弹入弹夹。栈的删除操作(pop)，叫作出栈，也有的叫作弹栈。
如同弹夹中的子弹出夹。
栈的顺序存储结构
栈的链式存储结构
栈的应用场景
1.子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，
回到原来的程序中。
2.处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆中。
3.表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4.二叉树的遍历。
5.冬形的深度优先(depth——first)搜索法。
用数组模拟栈
public class ArrayStackDemo {
public static void main(String[] args) {
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
",res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
default:
break;
}
}
System.out.println("程序退出！");
}}
//定义一个ArrayStack表示栈
class ArrayStack {
private int maxSize;
private int[] stack;
private int 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;
}
//入栈
public void push(int value){
if (isFull()){
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
//出栈
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
",i,stack[i]);
}
}
}
前缀(波兰)表达式
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。
eg：(3+4)*5-6对应的前缀表达式： - * + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，
用运算符对它们做相应计算（栈顶元素和次顶元素)，并将结果入栈;重复上述过程直到表达式最左端，
最后运算得出的值即为表达式的结果。
中缀表达式
1.需要创建两个栈:数栈存放数字，符号栈存放运算符
2.通过一个index值（索引)，来遍历我们的表达式
3.如果我们发现是一个数字,就直接入数栈
4.如果发现扫描到是一个运算符,就分如下情况:
如果当前的符号栈为空，就直接入栈。
如果符号栈有运算符，就进行比较:
①当前运算符的优先级<=栈中的操作符，就需要从数栈中pop出两个数再从符号栈中pop出一个运算
符，进行运算，将得到结果压入数栈，然后将当前运算符压入符号栈。
②当前运算符的优先级>栈中的操作符，就直接入符号栈。
5.当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
6.最后在数栈只有一个数字，就是表达式的结果
后缀表达式（逆波兰表达式）
后缀表达式与前缀表达式相似，只是在运算符位于操作数之后（3+4）*5-6对应的后缀表达式3 4 + 5 * 6 -
后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的
计算（次顶元素和栈顶元素），并将结果入栈;重复上述过程直到表达式最右端，最后运算得出的值即为表达式结果。
逆波兰计算器的实现
public class PolandNotation {
public static void main(String[] args) {
//将一个逆波兰表达式依次将数据和运算符放到ArrayList中
public static List<String> getListString(String suffixExpression) {
//分割suffixExpression
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<>();
for (String ele : split) {
list.add(ele);
}
return list;
}
//完成逆波兰表达式的运算
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);
}
}
return Integer.parseInt(stack.pop());
}}
将中缀表达式转换为后缀表达式
规则:从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分;若是符号，
则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出，
并将当前符号进栈，一直到最终输出后缀表达式为止。
思路：
1.初始化:运算符栈stack和动态数组(ArrayList) list;
2.从左至右扫描中缀表达式;
3.遇到操作数时，将其添加到list中
4.遇到运算符时，比较其与stack栈顶运算符的优先级:
如果stack为空，或栈顶运算符为左括号"(”，则直接将此运算符入栈;
如果优先级比栈顶运算符的高，也将运算符压入stack;
如果优先级比栈顶运算符的低，将stack栈中的所有运算符弹出并追加到list中。
5.遇列括号时:
如果是左括号"(”，则直接压入stack;
如果是右括号")”，则依次弹出stack栈顶的运算符，并追加到list中，直到遇到左括号为止，此时将这一对括号丢弃。
6.从左至右扫描中缀表达式结束后，将stack中剩余的运 算符依次追加到list中。
代码：
public static void main(String[] args) {
//中缀表达式转后缀表达式
String expression = "1+((2+3)*4)-5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println("中缀表达式~："+infixExpressionList);
List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
System.out.println("后缀表达式~："+suffixExpressionList);
System.out.printf("expression=%d
",calculate(suffixExpressionList));
public static List<String> toInfixExpressionList(String s) {
List<String> ls = new ArrayList<>();
int i = 0;
String str; //对多位数的拼接
char c;
do {
//如果是个非数字，加入ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++;
} else { //数字则主要考虑多位数
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;
}
public static int priority(String s){
if (s.equals("*") || s.equals("/")){
return 1;
}else if (s.equals("+")||s.equals("-")){
return 0;
}else {
return -1;
}
}
public static List<String> toInfixExpressionList(String s) {
List<String> ls = new ArrayList<>();
int i = 0;
String str; //对多位数的拼接
char c;
do {
//如果是个非数字，加入ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++;
} else { //数字则主要考虑多位数
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;
}
public static List<String> parseSuffixExpressionList(List<String> ls) {
Stack<String> s1 = new Stack<>();
List<String> s2 = new ArrayList<>();
for (String item : ls) {
//是数字，则加入数栈
if (item.matches("\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
//如果是右括号，则依次弹出s1栈顶的运算符，并压入s1，知道遇到“)”为之，此时将这对括号丢弃
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop(); //弹出s1栈，消除小括号
} else {
while(s1.size() != 0 && priority(item) <= priority(s1.peek())){
s2.add(s1.pop());
}
s1.push(item);
}
}