说起栈这个数据结构,马上想起“先进后出”(或“后进先出”),可以用数组或链表实现,是操作受限的,只能在集合的一段进行操作。

比如,拿一个数组来实现栈的话,会像这样。(右边是地址)

image20210720225426587.png

入栈的话,在下标为4的地方(上图未标出)加入元素;出栈的话,就从栈顶出栈。

数组模拟一个栈

下面这段代码是用数组简单地模拟一个栈,内容存放在数组中,里面有一个指向栈顶的指针。

class ArrayStack {
    /**
     * 栈顶。
     * 没有数据的时候表示-1
     */
    private int top = -1;
    /**
     * 栈的大小
     */
    private int maxSize;
    /**
     * 数组模拟栈,数据存放在该数组中
     */
    private int[] stack;

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

    /**
     * 栈是否满了
     *
     * @return
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 栈是否空了
     *
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("栈满");
        }
        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int item = stack[top];
        stack[top--] = 0;
        return item;
    }

    /**
     * 遍历这个栈
     */
    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 static void main(String[] args) {
    ArrayStack stack = new ArrayStack(10);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    stack.list();
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    stack.push(8);
    stack.push(9);
    stack.list();
}

运行结果如下。

stack[4]=5
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
5
4
stack[4]=9
stack[3]=8
stack[2]=3
stack[1]=2
stack[0]=1

栈计算中缀表达式

思想

我是用Java来写的,给定一个String,它是一条可能包括加、减、乘、除、括号的中缀表达式,计算出它的结果。

比如:3+2*4-5-11+(6-2)*2

使用的是一种通用的思想:双栈法。它用一个栈存放数字,一个栈存放符号。

算法步骤是这样的:

  1. 遍历字符串String
  2. 遇到数字,入数字栈。
  3. 若遇到符号:
    1. 若是普通符号(+、-、*、/):
      1. 当当前符号优先级小于等于符号栈顶的优先级,则计算之,直到不满足条件为止!
      2. 否则,就把符号入栈。
    2. 若是左括号,直接入符号栈。
    3. 若是右括号:
      1. 当符号栈栈顶元素不是左括号时,计算之,直到不满足条件为止。
    4. 最后,依次弹出符号栈的元素,计算之。
    5. 数字栈中的最后一个元素就是计算的结果。

PS:

  1. 关于优先级那块,其实代个符号就知道了。如果遍历到*,然后栈顶的元素是+或-,那肯定不用算,直接入栈;若遍历到的是+,然后符号栈顶的元素是*,那就先让乘*先计算了。也要注意,这里是循环的,因为这里总有一种“能算就算”的做法。
  2. 计算,其实是指从数字栈中弹出两个元素,符号栈中弹出一个元素,让他们进行计算,再把结果放回数字栈的过程。

代码

下面是可运行的代码。

// 存放优先级的集合
Map<Character, Integer> map = new HashMap<Character, Integer>() {{
    put('-', 1);
    put('+', 1);
    put('*', 2);
    put('/', 2);
    // 左括号要存一下,谨防有坑
    put('(', -1);
    put(')', -1);
}};

@Test
public void test() {
    // 结果应该是19
    String s = "13+2*(9-2)-1-7-1";
    Deque<Integer> numStack = new ArrayDeque<>();
    Deque<Character> opsStack = new ArrayDeque<>();
    int n = s.length();
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            // 读取数字,可判断多位数,如123
            int num = 0;
            int j = i;
            while (j < n && Character.isDigit(s.charAt(j))) {
                num = num * 10 + s.charAt(j++) - '0';
            }
            i = j - 1;
            numStack.push(num);
        } else if (c == '(') {
            opsStack.push(c);
        } else if (c == ')') {
            // 计算括号内的(即一直往前计算,直到找到左括号)
            while (!opsStack.isEmpty() && opsStack.peek() != '(') {
                cal(numStack, opsStack);
            }
            // 把最后一个左括号给去掉
            opsStack.pop();
        } else {
            // 若当前符号的优先级比栈顶的符号优先级低,那就计算
            while (!opsStack.isEmpty() && map.get(c) <= map.get(opsStack.peek())) {
                cal(numStack, opsStack);
            }
            // 否则就入栈,等着以后再算
            opsStack.push(c);
        }
    }
    // 最后再把所有可计算的全算了
    while (!opsStack.isEmpty()) {
        cal(numStack, opsStack);
    }
    System.out.println("结果为:" + numStack.pop());
}

/**
 * 辅助计算的函数
 * @param numStack 数字栈
 * @param opsStack 符号栈
 */
private void cal(Deque<Integer> numStack, Deque<Character> opsStack) {
    // 注意a、b的顺序,因为有a-b和a/b这种运算
    int b = numStack.pop();
    int a = numStack.pop();
    char ops = opsStack.pop();
    int res = 0;
    switch (ops) {
        case '+':
            res = a + b;
            break;
        case '-':
            res = a - b;
            break;
        case '*':
            res = a * b;
            break;
        case '/':
            res = a / b;
            break;
    }
    numStack.push(res);
}

栈计算后缀表达式

首先,什么是中缀表达式、后缀表达式呢?

中缀表达式就是我们平常看的,符号在中间的式子,比如1 + 1

后缀表达式就是把符号放在最后的,比如`1 1 +

同样,给定一个String类型的后缀表达式,如3 4 + 5 * 6 -,其实它是(3+4)*5-6转换过去的。

这个就很简单了,使用一个栈存数字,遇到一个符号就弹出两个数字出来计算,直到最后一个数字。

下面给出代码。

@Test
public void test() {
    String string = "3 4 + 5 * 6 -";
    String[] strings = string.split(" ");
    Deque<Integer> stack = new ArrayDeque<>();
    for (String s : strings) {
        // 匹配数字
        if (s.matches("\\d+")) {
            stack.push(Integer.valueOf(s));
        } else {
            // 计算
            int b = stack.pop();
            int a = stack.pop();
            // 不是数字,就是符号,而且符号是单个的
            char ops = s.charAt(0);
            int res = 0;
            switch (ops) {
                case '+':
                    res = a + b;
                    break;
                case '-':
                    res = a - b;
                    break;
                case '*':
                    res = a * b;
                    break;
                case '/':
                    res = a / b;
                    break;
            }
            stack.push(res);
        }
    }
    System.out.println("结果为:" + stack.pop());
}

这里超级容易,因为后缀已经是作好的优先级的处理,只需要遍历然后计算即可,而且它更符合计算机的思想。

中缀转后缀

我们既然知道后缀表达式容易计算,那应该想办法把中缀式转为后缀式,这样更方便计算机处理,因此下面介绍一下如何把中缀表达式转成后缀表达式,依然使用的是双栈法,不过过程可能与计算中缀有一点不同,但总体上一致。

思想

  1. 从左往后扫描中缀表达式
  2. 当是操作数时,压入符号栈。
  3. 当是运算符时:
    1. 遇到括号时:
      1. 如果是左括号,直接入符号栈
      2. 如果是右括号,依次弹出符号栈的元素,并压入数字栈,直到遇到左括号为止
    2. 遇到普通符号时
      1. 当符号栈为空时,入栈
      2. 否则若当前元素优先级比栈顶元素优先级高,同样入符号栈
      3. 否则,若当前元素的优先级小于等于栈顶元素,那就把符号栈顶元素弹出,加入到数字栈中,直到不满足条件为止。
  4. 重复上述步骤
  5. 最后,把数字栈中的元素倒序输出即为后缀表达式。

其实这个代码,把中缀式进行了转换,然后最终结果存在了数字栈中,

代码

Map<String, Integer> priority = new HashMap<String, Integer>() {{
    put("-", 1);
    put("+", 1);
    put("*", 2);
    put("/", 2);
    put("(", -1);
    put(")", -1);
}};

@Test
public void test2() {
    String string = "1 + ( ( 2 + 3 ) * 4 ) - 5";
    Deque<String> numStack = new ArrayDeque<>();
    Deque<String> opsStack = new ArrayDeque<>();
    String[] s = string.split(" ");
    for (int i = 0; i < s.length; i++) {
        if (s[i].matches("\\d+")) {
            numStack.push(s[i]);
        } else if ("(".equals(s[i])) {
            opsStack.push(s[i]);
        } else if (")".equals(s[i])) {
            while (!"(".equals(opsStack.peek())) {
                numStack.push(opsStack.pop());
            }
            // 把最后的 ( 弹出来
            opsStack.pop();
        } else {
            // 栈中能算的先算
            while (!opsStack.isEmpty() && priority.get(s[i]) <= priority.get(opsStack.peek())) {
                numStack.push(opsStack.pop());
            }
            // 不能算的,加入栈再说
            opsStack.push(s[i]);
        }
    }
    // 最后的元素
    while (!opsStack.isEmpty()) {
        numStack.push(opsStack.pop());
    }
    System.out.print("后缀表达式:");
    while (!numStack.isEmpty()) {
        System.out.print(numStack.pollLast());
    }
}

小结

计算式子、实现计算器是栈的一个典型使用,自我感觉它更多的是过程的一种模拟,当然这也和代码能力有关(可惜我很菜……),栈嘛,其实没什么,就是一个先进后出!不过你要知道它什么时候进,什么时候出而已。

API的使用,大致就是ArrayDeque这个工具,它既可以当作栈,又可以当作队列,以后可以专门讲讲这个集合,它是循环队列。