基本介绍1、栈是一个FILO先进后出的有序表2、栈是一种特殊的线性表，将线性表中元素的插入和删除限制在线性表的同一端。允许插入和删除的一端是变化端，称为栈顶（Top），另一端是固定端，称为栈底（Bottom）。3.根据栈的定义，第一个放入栈的元素在栈底，最后一个放入的元素在栈顶，删除元素正好相反。最后放入的元素先删除，最先放入的元素最后删除。栈的应用场景1.子程序调用：在调用子程序之前，会将下一条指令的地址存入栈中，子程序执行完毕后取出地址返回原处程序。2、处理递归调用：与子程序调用类似，不同之处在于栈中除了存放下一条指令的地址外，还会存放参数\区域变量等数据。3.表达式转换（中缀表达式到后缀表达式）和求值（实际解决）。4.二叉树遍历。5.图形的深度优先搜索算法。栈结构实现案例packagecom.structures.stack;importjava.util.Scanner;publicclassArrayStackDemo{publicstaticvoidmain(String[]args){ArrayStackstack=newArrayStack(4);Stringkey="";booleanloop=true;Scannerscanner=newScanner(System.in);while(loop){System.out.println("show:showstack");System.out.println("exit:退出程序");System.out.println("push:将数据入栈(intothestack)");System.out.println("pop:从栈中取出数据(outofthestack)");key=scanner.next();switch(key){case"show":stack.list();break;case"push":System.out.println("请输入数字");intvalue=scanner.nextInt();stack.push(value);break;case"pop":try{intres=stack.pop();System.out.println("Outofstackdata%d\n"+res);}catch(Exceptione){System.out.println(e.getMessage());}break;case"exit":scanner.close();loop=false;break;}}System.out.println("程序退出");}}//定义一个类来表示栈结构classArrayStack{privateintmaxSize;//栈的大小privateint[]stack;//数组模拟栈，数据放入数组privateinttop=-1;//top代表栈顶，初始化-1publicArrayStack(intmaxSize){this.maxSize=maxSize;stack=newint[this.maxSize];}//判断栈是否满publicbooleanisFull(){returntop==maxSize-1;}//判断栈是否为空publicbooleanisEmpty(){returntop==-1;}//入栈publicvoidpush(intvalue){if(isFull()){System.out.println("栈满");return;}top++;stack[top]=value;}//出栈publicintpop(){if(isEmpty()){thrownewRuntimeException("Stackisempty");}intvalue=stack[top];top--;返回ue;}//显示栈的状态【遍历栈】publicvoidlist(){if(isEmpty()){System.out.println("空栈，无数据~~");return;}for(inti=top;i>=0;i--){System.out.printf("stack[%d]=%d\n",i,stack[i]);}}}使用栈完成表达式（中缀表达式）的计算准备两个栈，数字栈和符号栈。1.通过一个索引值（index）遍历表达式。2.如果发现是数字，则直接装入数字栈。3.如果是符号，考虑情况。如果当前符号栈为空，则直接进入。如果符号栈有运算符，就会进行比较。如果当前运算符的优先级小于等于栈中的运算符，则需要从数栈中弹出两个数，然后从符号栈中弹出一个字符进行运算，结果放入号栈，然后将当前运算符放入符号栈。如果当前算子的优先级高于栈中的算子，则直接入栈。4.扫描到表达式时，依次从数栈和符号栈中弹出对应的数和符号，并运行。5.最后数栈中只有一个数，就是expression.packagecom.structures.stack的结果；publicclassCalculator{publicstaticvoidmain(String[]args){//表达式Stringexpression="700+2*6-2";//数栈ArrayStack2numStack=newArrayStack2(10);//符号栈ArrayStack2operStack=newArrayStack2(10);intindex=0;//用于扫描intnum1=0;intnum2=0;intoper=0;intres=0;charch='';//将每次扫描得到的char保存到chStringkeepNum="";//用于拼接多个数字while(true){ch=expression.substring(index,index+1).charAt(0);//如果是运算符if(operStack.isOper(ch)){//如果为空if(operStack.isEmpty()){operStack.push(ch);}else{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{//处理多个数字时，不能立即入栈。keepNum+=ch;//如果ch是表达式的最后一位if(index==expression.length()-1){numStack.push(Integer.parseInt(keepNum));}else{if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){numStack.push(Integer.parseInt(keepNum));keepNum="";}}}index++;//扫描结束退出if(index>=expression.length()){break;}}while(true){if(operStack.isEmpty()){break;}num1=numStack.pop();num2=numStack.pop();oper=operStack.pop();res=numStack.cal(num1,num2,oper);numStack.push(res);}System.out.printf("expression%s=%d\n",expression,numStack.pop());}}classArrayStack2{privateintmaxSize;//栈的大小privateint[]stack;//数组模拟栈，放数据入数组privateinttop=-1;//top表示顶部ofthestack,initialize-1publicArrayStack2(intmaxSize){this.maxSize=maxSize;stack=newint[this.maxSize];}//返回当前栈顶的值，不是poppublicintpeek(){returnstack[top];}//判断栈是否满publicbooleanisFull(){returntop==maxSize-1;}//判断栈是否为空publicbooleanisEmpty(){rreturntop==-1;}//堆栈publicvoidpush(intvalue){if(isFull()){System.out.println("堆栈已满");return;}top++;stack[top]=value;}//出栈publicintpop(){if(isEmpty()){thrownewRuntimeException("Stackisempty");}intvalue=stack[top];top--;returnvalue;}//显示栈的状态[遍历栈]publicvoidlist(){if(isEmpty()){System.out.println("空栈，无数据~~");return;}for(inti=top;i>=0;i--){System.out.printf("stack[%d]=%d\n",i,stack[i]);}}//返回运算符的优先级，数字越大，优先级越高。//假设当前operator只有+-*/publicintpriority(intoper){if(oper=='*'||oper=='/'){return1;}elseif(oper=='+'||oper=='-'){return0;}else{return-1;}}//判断是否为运算符publicbooleanisOper(charval){returnval=='+'||val=='-'||val=='*'||val=='/';}//计算方法publicintcal(intnum1,intnum2,intoper){intres=0;switch(oper){case'+':res=num1+num2;break;case'-':res=num2-num1;//注意sequencebreak;case'*':res=num1*num2;break;case'/':res=num2/num1;//注意sequencebreak;}returnres;}}[编辑推荐]酷，老大问我来开发一个简单的工作流引擎……Windows10将迎来翻天覆地的变化！今年第一波更新来了，2021年将迎来六大网络安全趋势，Windows10是近年来最新的大进步！先看Windows1021H2新特性小爱同学居然推出了PC版？带你体验电脑版小爱同学
