1. 栈的特点
  2. 栈的场景
  3. 栈的介绍
  4. Java实现
  5. 用数组实现
  6. 用链表实现（含尾插法和头插法）
  7. 场景应用
  8. 栈的表达形式（前缀、中缀、后缀）

以下只给出思路与关键方法，算法的源代码放在了git中，需要的自取

leidl97/algorithm-src

栈的特点

LIFO（后入先出）

《算法》将它比喻为桌子上的文件，后放上去的先拿起来阅读

img

出自《算法第四版》第78页

栈的场景

算术表达式求值，比如《算法第四版》所提到的Dijkstra的黄河算术表达式

img

《算法第四版》第81页

介绍

先入后出的一个有序列表

限制线性表中元素的插入和删除只能在同一端进行的特殊线性表。允许插入和删除的一端为变化的一端，成为栈顶（top），另一端为固定的一端成为栈底（bottom）

代码实现

可以用数组和链表的方式实现

用数组实现

定义变量3个，大小，栈顶，栈本身

方法定义4个，入栈，出栈，判断栈满，判断栈空

Java实现

属性定义

1
2
3
4
5
6
7
8
9
10
11
12
//栈顶
public int top;
//栈
public int[] stack;
//栈的大小
public int size;
//构造器
public MyStack(int size) {
    this.top = -1;
    this.size = size;
    this.stack = new int[this.size];
}

方法定义

入栈

1
2
3
4
5
6
7
8
9
//入栈
public void push(Object data) {
    if (isFull()) {
        System.out.println("栈满");
        return;
    }
    this.top++;
    this.stack[top] = data;
}

出栈

1
2
3
4
5
6
7
8
9
10
11
//出栈
public void pop() {
    if (isEmpty()) {
        System.out.println("栈空");
        return;
    }
    int val = this.stack[this.top];
    this.stack[top] = 0;
    this.top--;
    System.out.println("出栈成功："+val);
}

判断栈满

1
2
3
public boolean isFull() {
    return this.top == this.size - 1;
}

判断栈空

1
2
3
public boolean isEmpty() {
    return this.top == -1;
}

用链表方式实现

Java实现

属性定义

1
2
3
4
5
6
public int no;
public MyLinkedListStack next;
 
public MyLinkedListStack(int no) {
    this.no = no;
}

遍历实现

1
2
3
4
5
6
7
8
9
10
//遍历
public void show(){
    MyLinkedListStack cur = head;
    while (true) {
        if (cur.next == null) {
            break;
        }
        cur = cur.next;
        System.out.println(cur);
    }

尾插法（不推荐）

逆向思维，反人类，需要分情况讨论

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
//入栈---尾插法
public void push(MyLinkedListStack stack) {
    MyLinkedListStack cur = head;
    while (true) {
        if (cur.next == null) {
            break;
        }
        cur = cur.next;
    }
    cur.next = stack;
}

//出栈---尾插法
//分情况讨论，如果没有元素则提示栈空，如果只有一个元素则让该元素出栈，将该节点置为空
public void pop() {
    if (head.next == null) {
        System.out.println("栈空");
        return;
    }
    if (head.next.next == null) {
        System.out.println("出栈元素为："+head.next);
        head.next = null;
        return;
    }
    MyLinkedListStack cur = head;
    while (true) {
        if (cur.next.next == null) {
            System.out.println("出栈元素为："+cur.next);
            cur.next = null;
            break;
        }
        cur = cur.next;
    }
}

头插法（推荐）

简单，这里可见队列用尾插，栈用头插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//出栈---头插法
public void popHead() {
    if (head.next == null) {
        System.out.println("栈空");
        return;
    }
    System.out.println("出栈元素为："+head.next);
    head.next = head.next.next;
}

//入栈---头插法
public void pushHead(MyLinkedListStack stack) {
    stack.next = head.next;
    head.next = stack;
}

场景应用

用自定义栈来实现

给一个字符串表达式，输出最后计算结果

如：7*9-3+4/2+6-2

难点

①连续减法运算，需要考虑变号的情况

②数字为多位数运算情况

代码实现（中缀表达式）

获得字符优先级

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
//数字越大，优先级越高
public static final int plusPriority = 1;
public static final int subPriority = 1;
public static final int multiply = 2;
 
 
public static int getPriority(char c) {
    int priority = 0;
    switch (c) {
        case '*' :
            priority = Normal.multiply;
            break;
        case '/' :
            priority = Normal.multiply;
            break;
        case '+' :
            priority = Normal.plusPriority;
            break;
        case '-' :
            priority = Normal.subPriority;
            break;
        default:
            priority = 0;
    }
    return priority;
}

判断两个字符的优先级

1
2
3
4
5
6
7
8
public boolean isPriority(char c,Object o) {
    //c的优先级
    int cPriority = Normal.getPriority(c);
    //栈中元素的优先级
    int oPriority = Normal.getPriority((char)o);
    System.out.println(cPriority+":"+oPriority);
    return (cPriority-oPriority) > 0;
}

元素出栈操作

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
//出栈计算操作
public void before(char c, MyStack numStack, MyStack opreStack) {
    System.out.println("出栈计算");
    int num1 = (int)numStack.pop();
    int num2 = (int)numStack.pop();
    char c1 = (char)opreStack.pop();
    System.out.println(c);
    int result = 0;
    if (c1 == '*') {
        //后出来的操作之前出来的
        result = num1 * num2;
    } else if (c1 == '+') {
        result = num1 + num2;
    } else if (c1 == '-') {
        result = num2 - num1;
    }  else if (c1 == '/') {
        result = num2 / num1;
    } else {
        throw new RuntimeException("暂不支持该运算符");
    }
    //数字压入栈
    numStack.push(result);
    //操作符压入栈
    opreStack.push(c);
}

栈内的最后运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//栈内最后运算,，最后只会剩下加减运算
public void after(MyStack numStack, MyStack opreStack) {
    int num1 = (int)numStack.pop();
    int num2 = (int)numStack.pop();
    char c1 = (char)opreStack.pop();
    int result = 0;
    if (opreStack.top != -1) {
        //表示里面还有值，那么就去判断是否为-号，若为减法，则需要进行变号运算
        //对现有运算符进行变号
        if (c1 == '+') {
            c1 = (char)opreStack.stack[opreStack.top] == '-' ? '-' : c1;
        } else {
            c1 = (char)opreStack.stack[opreStack.top] == '-' ? '+' : c1;
        }
    }
    result = c1 == '+' ? num1 + num2 : num2 - num1;
    numStack.push(result);
}

主要的计算方法

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
public void computer(String str) {
    char[] array = str.toCharArray();
    MyStack numStack = new MyStack(array.length);
    MyStack opreStack = new MyStack(array.length);
    int isNum = 0;
    //加入一个判断多位数的标志
    int count = 0;
    //创建一个存放多位数的数组,，默认最多十位数
    int[] duo = new int[10];
    for (int j = 0; j < array.length; j++){
        char c = array[j];
        if (c >= '0' && c <= '9') {
            isNum = 1;//表示为数字
        } else {
            //若不为数字，将对位数组进行处理，然后压入栈
            if (count != 0) {
                int sum = 0;
                for (int i = 0; i < count; i++){
                    sum = sum + duo[count-i-1]*((int)Math.pow(10,i));
                }
                numStack.push(sum);
                count = 0;
            }
        }
        switch (isNum) {
            case 0 :
                if (opreStack.isEmpty()){
                    opreStack.push(c);
                    break;
                }
                if (isPriority(c,opreStack.stack[opreStack.top])) {
                    //如果传入的比栈中的优先级高则直接压入栈
                    System.out.println("压入栈");
                    opreStack.push(c);
                    break;
                }
                //否则进行出栈计算操作
                before(c,numStack,opreStack);
                break;
            default:
                duo[count] = c - '0';
                count++;
                //如果是遍历的最后一个元素则直接压入栈
                if (j == array.length - 1) {
                    numStack.push(c - '0');
                }
                break;
        }
        isNum = 0;
    }
    while (!opreStack.isEmpty()) {
        after(numStack, opreStack);
    }
    System.out.println(numStack);
    System.out.println(opreStack);
    System.out.println("该字符串["+str+"]运算的结果为："+numStack.stack[numStack.top]);
}

栈的表达形式

分为前缀表达式（波兰表达式），中缀表达式，后缀表达式（逆波兰表达式）

前缀表达式

举例说明：（3+4）x5-6对应的前缀表达式为- x + 3456

前缀表达式计算机求值规则

从右向左扫描，遇到数字时，将数字压入栈，遇到运算符的时候，弹出栈顶的两个数，用运算符对他们做相应的运算 （栈顶元素和次顶元素），并将结果入栈，重复上述过程直到扫描完，最后运算出的值即为前缀表达式的结果

中缀表达式

就是常见的运算表达式，比如（3+4）x5-6

人好理解，先+在x在-，但是计算机不好理解，还得进行判断优先级问题，往往会将中缀表达式转换为后缀表达式

后缀表达式（重要）

又称为逆波兰表达式，与前缀表达式相似，只是运算符位于操作符之后

比如（3+4）x5-6的后缀表达式为34+5x6-

与前缀不同的是后缀从左到右扫描，符合人类思维

计算机运算的时候应该为后缀表达式，但之前一直使用的是中缀表达式，所以需要先将中缀表达式转换为后缀表达式进行运算

运算规则

将传入的队列一次遍历，遇到数字入栈，遇到运算符则将栈顶两个数字出栈，与运算符进行计算，将计算的结果入栈，最后栈中最后一个数字为运算结果。

后缀转中缀

思路/规则

1、创建一个栈s1，用来存储运算符。一个队列s2，用来存放中间结果。

2、逐个扫描，如果栈为空，直接进入s1

3、如果为数字，则直接进入队列

4、如果为左括号，则直接入栈

5、如果为运算符，如果栈顶元素为运算符，那么比较优先级，若优先级小于等于栈顶元素，则将栈顶元素弹到队列中，否则直接入栈

6、如果为右括号，将栈中元素依次弹出，直到遇到左括号，最后将左括号弹出

7、输出队列s2，即为后缀表达式

使用代码验证如下中缀

中缀：1+(（2+3）x 4) - 5/ 对应的后缀1 2 3 + 4 * + 5 - / 对应的结果16

完成后使用代码完成一个更复杂的运算，包含多位数，加减乘除，小括号

img

上述表达式可以参照此图思路编写代码

整体代码部分

1、字符串转集合

2、集合转队列

3、队列进行运算

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
public class CenterToAfter {
    public static void main(String[] args) {
        //有多位数，加减乘除，小括号
        String before = "12+((2+3)*4)/4-5";//12, 2, 3, +, 4, *, 4, /, 5, -, +  / 12
        Queue<String> queue = todo(before);
        System.out.println("后缀转中缀的结果为：" + queue);
        String result = afterCal(queue);
        System.out.println("字符串表达式：【" + before + "】运算的结果为：" + result);
    }

    //中缀转后缀的算法
    public static Queue<String> todo(String before) {
        //创建栈s1
        Stack<String> stack = new Stack();
        //创建队列s2
        Queue<String> queue = new LinkedList();
        //第一步将传入的字符串转换为ArrayList
        //因为遍历起来好处理，处理多位数的情况
        List<String> list = stringToList(before);
        //遍历，按照规则进行
        for (int i = 0; i< list.size(); i++) {
            String cur = list.get(i);
            if (cur.matches("\\d+")){
                //如果为数字，则直接入队列
                queue.offer(cur);
            } else if ("(".equals(cur)){
                //如果为左括号，直接入栈
                stack.push(cur);
            } else if (stack.isEmpty()) {
                //如果栈为空则直接入栈
                stack.push(cur);
            } else if (")".equals(cur)) {
                //弹出栈中元素直到碰到左括号
                while (!stack.peek().equals("(")) {
                    queue.offer(stack.pop());
                }
                //非常重要！！！将左括号弹出栈，避免后续与运算符混合
                stack.pop();
            } else {
                //若栈顶元素不为左括号，则需要进行处理后入栈
                if (!stack.peek().equals("(")) {
                    int beforePriority = getPriority(stack.peek());
                    int nowPriority = getPriority(cur);
                    //若新运算符的优先级高，则直接入栈，否则将栈顶元素弹出到队列后入栈
                    if (nowPriority <= beforePriority) {
                        queue.offer(stack.pop());
                    }
                }
                stack.push(cur);
            }
        }

        //将栈中的剩余元素压入队列中
        while (!stack.isEmpty()) {
            queue.offer(stack.pop());
        }

        return queue;
    }

    //返回优先级，默认数字越大，优先级越高
    public static int getPriority(String s) {
        if ("+".equals(s) || "-".equals(s)) {
            return 0;
        } else if ("*".equals(s) || "/".equals(s)) {
            return 1;
        }else {
            throw new RuntimeException("暂不支持该运算符："+s);
        }
    }

    //字符串转集合的方法
    public static List<String> stringToList(String before){
        List<String> result = new ArrayList();
        char[] cs = before.toCharArray();
        String string = "";
        //判断上个是否为数字
        boolean flag = false;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] >= '0' && cs[i] <= '9') {
                //如果为数字，那么字符串相加
                string += cs[i];
                flag = true;
                if (i == cs.length-1) {
                    result.add(string);
                    break;
                }
            } else {
                if (flag) {
                    //先将数字部分存入集合
                    result.add(string);
                    string = "";
                }
                //那么不为数字，直接存入list
                result.add(cs[i] + "");
                flag = false;
            }
        }
        return result;
    }

    //后缀计算方法
    public static String afterCal(Queue<String> param) {
        //用来计算的栈
        Stack<String> stack = new Stack();
        //结果
        int result = 0;
        for (String str : param) {
            if (str.matches("\\d+")) {
                //如果为数字则直接入栈
                stack.push(str);
            } else {
                //为运算符，进行计算后入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());

                switch (str) {
                    case "+" :
                        result = num1 + num2;
                    break;
                    case "-" :
                        result = num1 - num2;
                    break;
                    case "*" :
                        result = num1 * num2;
                    break;
                    case "/" :
                        result = num1 / num2;
                    break;
                    default:
                        throw new RuntimeException("没有该运算符");
                }
                stack.push(String.valueOf(result));
            }
        }
        return stack.peek();
    }
}

效果截图

img