一、概念

  1. 栈是一个先入后出(FILO)的有序列表。
  2. 栈限制线性表中元素的插入和删除只能在同一端进行，并将此端称为栈顶，而另一端为固定的一端，称为栈底。

image.png

二、栈的应用场景

  1. 子程序的调用：在跳往子程序之前，会先将下一个指令的地址存放到堆栈中，直到子程序执行完之后再将地址取出，以回到原来的程序中。
  2. 处理递归调用：和子程序调用类似，但会将参数、区域变量等数据也存入堆栈中。
  3. 表达式的转换与求值。
  4. 二叉树的遍历。
  5. 图的深度优先(depth-first)遍历。

三、代码实现

3.1 使用数组实现栈

package a04.arrayStack;

public class ArrayStack {
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //栈满
    public boolean isFull() {
        return top + 1 == maxSize;
    }

    //栈空
    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 result = stack[top];
        top--;
        return result;
    }

    //显示栈
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        //从栈顶遍历
        for (int i = top; i >= 0; i--) {
            System.out.printf("%d\t", stack[i]);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(10);
        for (int i = 0; i < 10; i++) {
            arrayStack.push(i);
        }
        arrayStack.show();

        for (int i = 0; i < 10; i++) {
            arrayStack.pop();
        }
        arrayStack.show();
    }
}

3.2 链表实现栈

package a04.arrayStack;

public class LinkedStack {
    StackNode head;
    int maxSize;
    int size;

    public LinkedStack(int maxSize) {
        this.maxSize = maxSize;
    }

    //栈满
    public boolean isFull() {
        return size == maxSize;
    }

    //栈空
    public boolean isEmpty() {
        return size == 0;
    }

    //入栈
    public void push(int num) {
        if (isFull()) {
            System.out.println("栈满");
        }
        StackNode node = new StackNode(num);
        //考虑第一个节点的特殊性
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
        size++;
    }

    //出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int result = head.num;
        head = head.next;
        size--;
        //考虑最后一个节点的特殊性
        if (size == 0) {
            head = null;
        }
        return result;
    }

    //显示栈
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        StackNode temp = head;
        while (true) {
            System.out.printf("%d\t",temp.num);
            if (temp.next == temp ) {
                break;
            }
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedStack linkedStack = new LinkedStack(10);
        for (int i = 0; i < 10; i++) {
            linkedStack.push(i);
        }
        linkedStack.show();

        for (int i = 0; i < 10; i++) {
            linkedStack.pop();
        }
        linkedStack.show();
    }

}

class StackNode {
    int num;
    StackNode next = this;

    public StackNode(int num) {
        this.num = num;
    }
}

四、实战

4.1 使用栈来计算表达式

7 * 2 * 2 - 5 + 1 - 5 + 3 - 4

思路
  1. 使用两个栈来处理，一个数栈，一个运算符栈，遍历表达式并将其拆放入栈。
  2. 符号进栈时，若符号栈为空或者比栈内符号优先级高，就直接入栈
  3. 若优先级较栈内低，则将数栈中取两个数与栈内符号运算，然后将结果如数栈，将符号入符号栈。
  4. 当表达式遍历完毕，按顺序的将数栈与符号栈的符号进行运算，并将结果入数栈。
  5. 最后数栈只有1个值，即结果。

中缀表达式

package a04.calculator;

public class Calculator {
    public static void main(String[] args) {
        String expression = "30+2*6-2";
        CalStack numStack = new CalStack(10);
        CalStack opStack = new CalStack(10);
        int result = 0;
        String keepNumber = "";//用于处理多位数
        for (int i = 0; i < expression.length(); i++) {
            char temp = expression.charAt(i);
            //如果是运算符
            if (opStack.isOperator(temp)) {
                //看符号栈是否空
                if (opStack.isEmpty()) {
                    opStack.push(temp);
                } else {
                    //符号栈非空
                    //对比符号优先级
                    if (opStack.priority(temp) <= opStack.priority(opStack.peek())) {
                        //当前符号优先级小
                        int a = numStack.pop();
                        int b = numStack.pop();
                        result = opStack.cal(a, b, opStack.pop());
                        numStack.push(result);
                        opStack.push(temp);
                    } else {
                        //当前符号优先级高
                        opStack.push(temp);
                    }
                }
            } else {
                //如果不是最后一位数字，且下一个字符是数字，则先拼接，暂不入数栈
                keepNumber = keepNumber + temp;
                if (i != expression.length()-1) {
                    if(Character.isDigit(expression.charAt(i+1))){
                        continue;
                    }
                }
                numStack.push(Integer.valueOf(keepNumber));
                keepNumber="";

            }
//            System.out.println("---------|"+temp+" |----------");
//            System.out.print(" 数栈:");
//            numStack.show();
//            System.out.print(" 符号栈:");
//            opStack.show();
        }

        while (true) {
            if (opStack.isEmpty()) {
                break;
            }
            result = opStack.cal(numStack.pop(), numStack.pop(), opStack.pop());
            numStack.push(result);
        }
        System.out.println(result);
    }
}


//数栈
class CalStack {
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public CalStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //栈满
    public boolean isFull() {
        return top + 1 == maxSize;
    }

    //栈空
    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 result = stack[top];
        top--;
        return result;
    }

    //显示栈
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        //从栈顶遍历
        for (int i = top; i >= 0; i--) {
            System.out.printf("%d\t", stack[i]);
        }
        System.out.println();
    }

    //返回运算符的优先级，数字越大， 则优先级越高
    public int priority(int operator) {
        if (operator == '*' || operator == '/') {
            return 20;
        } else if (operator == '+' || operator == '-') {
            return 10;
        } else {
            //假定目前运算符只有+ - * /
            return -1;
        }
    }

    //判断是不是一个运算符
    public boolean isOperator(int operator) {
        return operator == '+' || operator == '-' || operator == '/' || operator == '*';
    }

    //计算方法
    public int cal(int a, int b, int operator) {
        int result = 0;
        switch (operator) {
            case '+':
                result = a + b;
                break;
            case '-':
                //注意顺序，栈是先进后出
                result = b - a;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = b / a;
                break;
        }
        return result;
    }


    //返回当前栈顶的值，不出栈
    public int peek() {
        return stack[top];
    }
}

五、三种表达式

5.1 前缀表达式

  1. 波兰表达式，前缀表达式的运算符位于操作数之前。
  2. (3+4)*5-6对应的前缀表达式是-x+3456。
  3. 求值时，从右至左扫描表达式，先将数字全部入栈，遇到符号时，将数栈的两个值弹出并与符号计算，结果重新入数栈。

5.2 中缀表达式

  1. 是人类最熟悉的表达式，如(3+4)*5-6。
  2. 中缀表达式经常需要判断运算符的优先级。
  3. 对计算机来说不好操作，往往需要转换成另一种表达式进行运算，一般转换成后缀表达式。

5.3 后缀表达式

  1. 也称逆波兰表达式，将运算符置于操作数之后。
  2. (3+4)*5-6 对应的后缀表达式是34+5x6-。
  3. 求值时，从左向右扫描，遇到数字时入栈，遇到符号时，将数栈的两个值弹出并与符号计算，结果重新入数栈。

5.4 逆波兰计算器

package a04.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Reverse Polish Notation:   逆波兰表达式计算器
public class RPNCalculator {

    public static void main(String[] args) {
        //(3+4)*5-6 => 34+5x6-
        String suffixExpression = "3 4 + 5 * 6 -";
        //1.先放入ArrayList中。
        List<String> rpnList = getListString(suffixExpression);
        //2.将ArrayList传给一个方法，在方法中配合栈完成计算。
        int result = calculate(rpnList);
        System.out.println(result);
    }

    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String item : split) {
            list.add(item);
        }
        return list;
    }

    public static int calculate(List<String> rpnList) {
        Stack<String> stack = new Stack<>();
        for (String item : rpnList) {
            //使用正则表达式判断是不是数字
            if (item.matches("\\d+")) {
                //是数字就入栈
                stack.push(item);
            } else {
                //是符号就运算
                int b = Integer.valueOf(stack.pop());
                int a = Integer.valueOf(stack.pop());
                int result = 0;
                if (item.equals("+")) {
                    result = a + b;
                } else if (item.equals("-")) {
                    result = a - b;
                } else if (item.equals("*")) {
                    result = a * b;
                } else if (item.equals("/")) {
                    result = a / b;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(result + "");
            }
        }
        return Integer.valueOf(stack.pop());
    }
}

5.5 中缀转后缀

不要纠结思路的来源，如何转是已有的规范。

  1. 初始化两个栈，符号栈s1和存放过程的中间栈s2。
  2. 从左到右扫描表达式。
  3. 遇到操作数，压入s2
  4. 遇到符号，与s1栈内符号比较优先级：
    1. s1为空，或栈顶为(，则将符号压入s1.
    2. 优先级比s1栈顶高，也压入s1.
    3. 否则，将s1栈顶的运算符弹出并压入s2，并回到步骤4继续做比较。
  5. 遇到括号时
    1. 如果是(，压入s1
    2. 如果是），依次弹出s1栈顶的符号并压入s2，直到遇到左括号，并将此对括号丢弃。
  6. 扫描完表达式，将s1中剩余的符号依次压入s2，s2为后缀表达式。
package a04.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InToSuf {
    public static String inToSuf(List<String> infixList) {
        //操作符栈
        Stack<String> charStack = new Stack<>();
        String result = "";

        for (int i = 0; i < infixList.size(); i++) {
            String item = infixList.get(i);
//            System.out.println("i== " + i + "  item= " + item);
//            System.out.println(charStack);
            //如果是操作数，拼入结果
            if (item.matches("\\d+")) {
                result = result + " " + item;

            } else if (item.equals("+") || item.equals("-") || item.equals("*") || item.equals("/")) {
                //如果是操作符
                //如果符号栈为空或栈顶为(,则将符号压入符号栈
                if (charStack.isEmpty() || charStack.peek().equals("(")) {
                    charStack.add(item);
                } else if (priority(item) > priority(charStack.peek())) {
                    //优先级比栈顶高，也将符号压入符号栈
                    charStack.add(item);
                } else {
                    result = result + " " + charStack.pop();
                    i--;
                }
            } else if (item.equals("(")) {
                //如果是左括号，压入符号栈
                charStack.add(item);
            } else if (item.equals(")")) {
                //如果是右括号，依次弹出s1栈顶的符号拼入结果，直到遇到左括号
                while (true) {
                    if (charStack.peek().equals("(")) {
                        break;
                    }
                    result = result + " " + charStack.pop();
                }
                //并将此对括号丢弃
                charStack.pop();
            } else {
                throw new RuntimeException("操作符异常");
            }
        }
        //将s1中剩余的符号依次拼入结果
        while(true){
            if(charStack.isEmpty()){
                break;
            }
            result = result + " " + charStack.pop();
        }

        return result;
    }

    //返回运算符的优先级，数字越大， 则优先级越高
    public static int priority(String operator) {
        if (operator.equals("*") || operator.equals("/")) {
            return 20;
        } else if (operator.equals("+") || operator.equals("-")) {
            return 10;
        } else {
            //假定目前运算符只有+ - * /
            return -1;
        }
    }

    public static List<String> getListString(String infixExpression) {
        String[] split = infixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String item : split) {
            list.add(item);
        }
        return list;
    }

    public static void main(String[] args) {
        String infixExpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
        List<String> infixList = getListString(infixExpression);
//        System.out.println(infixList);
        String result = inToSuf(infixList);
        System.out.println(result);
    }
}

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议