栈

栈的介绍

• 栈的英文（stack）
• 栈是一个先入后出的有序列表
• 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。
• 根据栈的定义，最先放入栈中元素在栈底，最后放入栈中元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
  

实现栈的思路分析

1.使用数组来模拟栈

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

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

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

package com.xxxx.stack;import java.util.Scanner;public class ArrayStackDemo {public static void main(String[] args) {// 测试一下//先创建一个ArrayStack对象表示栈ArrayStack stack=new ArrayStack(4);String key="";boolean loop=true;//控制是否退出菜单Scanner sc=new Scanner(System.in);while(loop) {System.out.println("show:表示显示栈");System.out.println("exit:退出程序");System.out.println("push:表示添加数据到栈（入栈）");System.out.println("pop:表示从栈取出数据（出栈）");key=sc.next();switch(key) {case "show":stack.list();break;case "push":System.out.println("请输入一个数");int value=sc.nextInt();stack.push(value);break;case "pop":try {int res=stack.pop();System.out.printf("出栈的数据是%d\n",res);				}catch(Exception e) { System.out.println(e.getMessage());}break;case "exit":loop=false;break;default:break;}}System.out.println("程序退出~~~");}
}
//定义一个ArrayStack表示栈
class ArrayStack{private int maxSize;//栈的大小private int[] stack;//数组，数组模拟栈，数据就放在该数组private int top=-1;//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;}//入栈-pushpublic void push(int value) {//先判断栈是否满if(isFull()) {System.out.println("栈满");return;}top++;stack[top]=value;}//出栈-poppublic 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]);}}
}

栈实现综合计算器思路分析

package com.xxxx.stack;public class Calculator {public static void main(String[] args) {
//			根据前面老师的思路，完成表达式的运算String str="2000+20*5";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循环的扫描strwhile(true) {
//			依次得到str的每一个字符ch=str.charAt(index);//判断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(res);operStack.push(ch);}else {//如果当前的操作符的优先级大于栈中优先级，就直接入符号栈。operStack.push(ch);}}else {//如果为空直接入栈。。operStack.push(ch);}}else {//如果是数字的话就直接入数字栈
//					numStack.push(ch-48);/** 分析思路：* 1.当处理多位数时，不能发现一个数字就立即入栈，因为他可能是多位数 * 2.在处理数，需要向str的表达式的index后再看一位，如果是数就进行扫描，如果是符号才入栈* 3.因此我们需要定义一个变量字符串，用于拼接*///处理多位数keepNum+=ch;//如果ch已经是str的最后一位，就直接入栈if(index==str.length()-1) {numStack.push(Integer.parseInt(keepNum));}else {//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈//注意是看后一位，不是index++;if(operStack.isOper(str.charAt(index+1))){//如果后一位是运算符，则入栈numStack.push(Integer.parseInt(keepNum));//重要的是！！！！，将keepNum清空keepNum="";}}	}
//			让index+1，并判断是否扫描到str的最后index++;if(index>=str.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);//入栈}System.out.printf("表达式%s=%d",str,numStack.peek());}
}
//先创建一个栈，直接使用前面创建的
//定义一个ArrayStack表示栈
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]; }//栈满public boolean isFull() {return top==maxSize-1;}//栈空public boolean isEmpty() {return top==-1;}//入栈-pushpublic void push(int value) {//先判断栈是否满if(isFull()) {System.out.println("栈满");return;}top++;stack[top]=value;}//出栈-poppublic int pop() {//先判断栈是否为空if(isEmpty()) {throw new RuntimeException("栈空，没有数据");}int value=stack[top];top--;return value;}//增加一个方法，可以返回当前栈顶的值，但是不是真正pop，不会删除当前栈顶public int peek() {//先判断栈是否为空if(isEmpty()) {throw new RuntimeException("栈空，没有数据");}int value=stack[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]);}}//返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示//数字越大，则优先级就越高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) {int res=0;//res用于存放计算的结果switch (oper) {case '+':res=num1+num2;break;case '-':res=num2-num1;//注意顺序break;case '*':res=num1*num2;break;case '/':res=num2/num1;break;default:break;}return res;}
}