栈的定义和应用

1、定义

• 栈是一个先入后出的有序列表
• 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
• 最先放入的元素在栈底，且最后出栈。最后放入的元素在栈顶，且最先出栈

2、应用场景

• 子程序递归调用。如JVM中的虚拟机栈
• 表达式转换（中缀转后缀）与求值
• 二叉树的遍历
• 图的深度优先遍历

3、实现

用数组实现

思路

• 定义top表示栈顶，初始值为-1
• 入栈的操作，先让top++，再放入数组
• 出栈操作，先取出元素，在让top–
• top == -1时，栈空
• top == maxSize-1时，栈满

代码

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(4);
        String key = "";
        boolean flag = true;
        Scanner scanner = new Scanner(System.in);

        while (flag){
            System.out.println("输入show展示数据");
            System.out.println("输入push加入数据");
            System.out.println("输入pop 取出数据");
            System.out.println("输入exit退出程序");
            key = scanner.next();
            switch (key){
                case "show":
                    arrayStack.showStack();
                    break;
                case "push":
                    System.out.println("请输入您的数据:");
                    int value = scanner.nextInt();
                    arrayStack.pushStack(value);
                    break;
                case "pop":
                    try {
                        int num = arrayStack.popStack();
                        System.out.println("取出的数据是:"+num);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序已退出");
    }
}

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 pushStack(int value){
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    public int popStack(){
        if (isEmpty()){
            throw new RuntimeException("栈空,无法取出");
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void showStack(){
        if (isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >= 0; i--){
            System.out.printf("stack[%d]=%d \n",i,stack[i]);
        }
    }
}

4、应用

表达式求值

思路

• 准备一个索引index来帮助我们遍历表达式
• 如果index位置上的元素是一个数字，就直接入栈
• 如果index位置上的元素是一个符号
  • 如果符号栈为空，直接入栈
  • 如果符号栈不为空
    • index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，并将index位置上的符号压入符号栈
    • index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
• 当表达式遍历完毕后，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
• 最终数栈中只有一个值，这个值便是运算结果
• 注意：
  • 读取的是字符，所以存入数字前需要减去0的ASCII码
  • 如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈

代码

public class Calculator {
    public static void main(String[] args) {
        String  expression = "321+2*6-2";
        //要获取两个栈,一个是数栈,一个是符号栈
        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 (true){
            //依次得到expression的每一个字符
            ch = expression.substring(index,index+1).charAt(0);

            if (operStack.isOper(ch)){//判断这个扫描到的字符是不是运算符
                if (!operStack.isEmpty()){//判断这个符号栈是否为空
                    /*
                    如果符号栈不为空
                    index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。
                    将运算结果放入数栈中，并将index位置上的符号压入符号栈
                    index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
                     */
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())){
                        num1 = numStack.popStack();
                        num2 = numStack.popStack();
                        oper = operStack.popStack();
                        res = numStack.cal(num1,num2,oper);
                        numStack.pushStack(res);
                        operStack.pushStack(ch);
                    }else {
                        //如果优先级比栈顶的要大,则直接入符号栈
                        operStack.pushStack(ch);
                    }
                }else {
                    //为空的话直接入符号栈
                    operStack.pushStack(ch);
                }
            }else {//是数的情况
                keepNum += ch;

                if (index == expression.length()-1){//如果ch已经是最后一个字符了,直接入栈
                    numStack.pushStack(Integer.parseInt(keepNum));
                }else {
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        //下一个字符是运算符时就入栈
                        numStack.pushStack(Integer.parseInt(keepNum));
                        keepNum = "";//入栈后一定要制空字符串
                    }
                }
            }
            index++;
            if (index == expression.length()){//如果扫描完了则退出循环
                break;
            }
        }
        while (true){
            if (operStack.isEmpty()){//如果符号栈空了就运算结束,数栈的最后一个数就是最终结果
                break;
            }
            num1 = numStack.popStack();
            num2 = numStack.popStack();
            oper = operStack.popStack();
            res = numStack.cal(num1,num2,oper);
            numStack.pushStack(res);
        }
        res = numStack.popStack();
        System.out.printf("表达式: %s=%d",expression,res);
    }
}

class ArrayStack2{
    private int maxSize;
    private int[] stack;
    private int 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;
    }

    public int peek(){
        return stack[top];
    }

    public void pushStack(int value){
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    public int popStack(){
        if (isEmpty()){
            throw new RuntimeException("栈空,无法取出");
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void showStack(){
        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;
        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;
    }
}