提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

什么是栈

1.栈是一个先入后出 的有序列表

2.栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。 栈中允许插入和删除的一端，为变化端，称为栈顶，另外一端为固定的一端，称为栈底

3.最先放入的元素放在栈的底部，最后放入的元素在栈顶。 这样也就形成先放入的元素后取出，后放入的元素先取出。

4.图解出栈（pop） 和 入栈（push）

使用数组模拟栈 、链表模拟栈 、使用栈完成 表达式的计算

提示：以下是本篇文章正文内容，下面案例可供参考

一、数组模拟栈

思路：

1. 创建一个类 定义一个top来表示栈顶。定义一个数组用来存放添加的数据，在顶一个一个数组容量 用来设置数组最大（maxSize）

2. 通过构造器传入maxSize ， 并对数组和top进行初始化 top=-1 （top不一定一定要是-1可以是0 如果是0 ，第3点的top就不用先++，第四步的top要先--） 并创建满栈满和栈空判断 的方法

3. 入栈的操作当有数据进入栈是，top++；给数组[top]赋值

4. 出栈操作 return 数组[top--]

1.创建类ArrayStack

class ArrayStack{
    private int Maxtop;//栈的最大容量
    private int [] Stack;//数据存放的数组
    private int top;//栈顶
    //在构造器中完成初始化
    public ArrayStack(int maxtop) {
        Maxtop = maxtop;
        Stack=new int[maxtop];
        top=-1;
    }
    //判断栈是否满
    public boolean isFull(){
        return top==Maxtop-1;
    }

    //判断栈是否为空
    public boolean isNull(){
        return top==-1;
    }
}

2.入栈出栈和遍历元素

  //入栈
    public void push(int value){
        //先加后用
        if (isFull()) {
            System.out.println("栈满 ");
            return;
        }
        Stack[++top]=value;
    }

    //出栈
    public int pop(){
        if (isNull()) {
            throw new RuntimeException("栈为空");
        }
        //先用后减
        return Stack[top--];
    }

    //遍历栈
    public void list(){
        if (isNull()){
            System.out.println("空");
            return;
        }
        //需要从栈顶开始显示数据
        for (int i = top; i>=0 ; i--) {
            System.out.println(Stack[i]);
        }
    }

3.main方法的调用

public static void main(String[] args) {
        //测试
        ArrayStack arystack = new ArrayStack(4);//给4个大小
        String key="";
        boolean loop=true;
        Scanner in = new Scanner(System.in);
        while (loop){
            System.out.println("入栈push ");
            System.out.println("出栈pop ");
            System.out.println("遍历show ");
            System.out.println("退出exit ");
            key= in.next();
            switch (key){
                case "show":
                    arystack.list();
                    break;
                case "pop":
                    try {
                        int pop = arystack.pop();
                        System.out.println(pop);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }

                    break;
                case "push":
                    System.out.println("输入要添加的值");
                    arystack.push(in.nextInt());
                    break;
                case "exit":
                    loop=false;
                    in.close();
                    break;
                default:
                    System.out.println("输入有误");
            }
        }
    }

二.链表模拟栈

思路：

1. 定义一个node(节点)类
2. 节点类包含 value值 和 pre域指向上一个节点
3. 在调用类中 创建节点对象 保证这个节点对象一直是指向最后一个节点
4. 添加元素都要将新元素的pre指向节点对象 然后将新节点赋予节点对象（因为是从前向后 我们得让节点对象始终都是最后一个节点域
5. 取出元素  用一个临时变量保存value值 将节点对象指向pre一个节点 return临时变量
6. 遍历用一个临时节点（temp）获取节点对象 如果temp不等于null 就循环输出value值 然后temp=temp.next

1.创建节点类

class  PreNode{
   public int value;
   public PreNode pre;

    public PreNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "value=" + value ;
    }
}

2.方法类

class PreLinkedList{
    //节点对象 保证这个节点对象一直是指向最后一个节点
    PreNode preNode;

    public void push(PreNode newnode){
        newnode.pre=preNode;
        preNode=newnode;
    }
    //是否为空
    public boolean isNull(){
        return preNode==null;
    }

    public int pop(){
        if (isNull()){
            throw new RuntimeException("节点为空");
        }
        int value= preNode.value;
        preNode=preNode.pre;
        return value;
    }


    public void show(){
        PreNode temp=preNode;
        if (isNull()){
            System.out.println("节点为null");
            return;
        }
        while (temp!=null){
            System.out.println(temp.value);
            temp=temp.pre;
        }
    }

}

 main方法在数组的基础上改动一下就行

三.用栈计算表达式

1.创建两个静态的Stack对象

static Stack<Integer> numStack=new Stack();
static Stack<Character> operStack=new Stack();

2.判断字符串优先级

    //返回运算符的优先级
    public static int priority(int oper){
        if (oper=='*'||oper=='/'){
            return 1;
        }else if (oper=='+'||oper=='-'){
            return 0;
        }else {
            return -1;
        }
    }

3.判断该字符是不是一个运算符

    //判断是不是一个运算符
    public static boolean isOper(char val){
        return val=='*'||val=='-'||val=='+'||val=='/';
    }

4.对进行运算

    public static int cal(int num1,int num2,char val){

        switch (val){
            case '*':
                return num1*num2;

            case '/':
                return num1/num2;

            case '+':
                return num1+num2;

            case '-':
                return num1-num2;
        }
        return 0;
    }

5.main方法中的调用（重要）

 对字符串进行循环遍历

思路：

 public static void main(String[] args) {
        String str="700-100+100*2";
        int num1=0;//保存从numStack取出的变量
        int num2=0;//保存从numStack取出的变量
        int res=0;//返回num1 num2 之间的运算结果
        for (int i = 0; i <str.length() ; i++) {
            

            //--判断运算符
            char c = str.charAt(i);
            if (isOper(c)){

                if (!operStack.empty()){
                    if (priority(c)<=priority((char)operStack.peek())){
                        num2=numStack.pop();
                        num1=numStack.pop();
                        res=cal(num1,num2,operStack.pop());
                        numStack.push(res);
                        operStack.push(c);
                    }else {
                        operStack.push(c);
                    }
                }else {
                    operStack.push(c);
                }

            }
            //判断运算符
            //--判断不是运算符的多位数
            else {
                for (int j = i; j < str.length(); j++) {
                    char d = str.charAt(j);
                    if (isOper(d)) {
                        numStack.push(Integer.valueOf(str.substring(i, j)));
                        i=j-1;
                        break;
                    }
                    if(j+1==str.length()){
                        numStack.push(Integer.valueOf(str.substring(i, j+1)));
                        i=j;
                    }
                }
            }
            //--判断不是运算符的多位数
        }

        //遍历 运算符栈中的运算符 
        while (operStack.size()>0){
            num2=numStack.pop();
            num1=numStack.pop();
            res=cal(num1,num2,operStack.pop());
            numStack.push(res);
        }

        System.out.println(str+"="+numStack.pop());
    }