【数据结构与算法】stack栈的介绍和实现、使用栈来实现中缀表达式求值

1. 栈的介绍

栈是一个先入后出的有序列表。允许插入(入栈push)和删除(出栈pop)的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)

2. 栈的应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
表达式(中缀表达式转后缀表达式)的转换与求值
二叉树的遍历
图形的深度优先(depth-first)搜索法

3. 栈的实现

使用数组模拟栈的使用，思路如下：

定义一个top来表示栈顶，初始化为-1
当有数据加入到栈时，top++，stack[top] = 数据
当从栈中取出数据时，int value = stack[top]，top–

实现如下：

import java.util.Scanner;

public class ArrayStackDemo {

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(3);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;

        System.out.println("show: 表示显示栈");
        System.out.println("exit: 退出程序");
        System.out.println("push: 表示入栈");
        System.out.println("pop: 表示出栈");
        System.out.println("请输入你的选择：");

        while (loop) {
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.show();
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int inputData = scanner.nextInt();
                    stack.push(inputData);
                    break;
                case "pop":
                    try {
                        int outData = stack.pop();
                        System.out.printf("出栈的数据是%d\n", outData);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    System.out.println("程序退出");
                    break;
                default:
                    break;
            }
        }

    }

}

// 用数组实现的栈
class ArrayStack {
    // 栈的最大元素数量
    private int maxSize;
    private int[] stack;
    private int top = -1;

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

    // 判断栈是否满了
    public boolean isFull() {
        return this.top == this.maxSize - 1;
    }

    // 判断栈是否空的
    public boolean isEmpty() {
        return this.top == -1;
    }

    // 入栈push
    public void push(int data) {
        // 先判断栈是否满了
        if (this.isFull()) {
            System.out.println("栈满了");
            return;
        }
        this.top++;
        this.stack[this.top] = data;
    }

    // 出栈pop
    public int pop() {
        // 先判断栈是否空
        if (this.isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int data = this.stack[this.top];
        this.top--;
        return data;
    }

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

运行程序，结果如下：

show: 表示显示栈
exit: 退出程序
push: 表示入栈
pop: 表示出栈
请输入你的选择：
push
请输入一个数
10
show
stack[0]=10
pop
出栈的数据是10
exit
程序退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. 使用栈实现中缀表达式的转换与求值

需求说明：输入一个字符串的表达式，如7*2*2-5+1-5+3-4，我们需要对这个字符串的表达式进行转换，然后求值。这个时候就可以使用栈解决。目前只处理+、-、*、/四个运算符，且字符串表达式不包含空格

使用栈完成表达式计算的思路：

通过一个index索引值，来遍历我们的表达式
如果是一个数字，就直接入数栈
如果是一个符号，情况如下：
1. 如果当前的符号栈为空，就直接入符号栈
2. 如果符号栈有运算符，就进行运算符优先级的比较。如果当前运算符的优先级小于或等于栈中的运算符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行计算，再将计算的结果入数栈，然后将当前的运算符入符号栈；如果当前的运算符的优先级大于栈中的运算符，就直接入符号栈
当遍历完表达式，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行计算
最后在数栈只有一个数字，就是表达式的结果