栈

栈

栈(stack)

  • 栈是一个先入后出的有序列表
  • 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
  • 根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
栈的思路分析
  • 使用数组来模拟栈
  • 定义一个top来表示栈顶，初始化为-1
  • 入栈的操作，当有数据加入到栈时，top++;stack[top]=value;
  • 出栈的操作，int value=stack[top];top–;return value;
数组模拟栈
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
import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true;// 控制是否退出菜单
        Scanner sc = new Scanner(System.in);
        while (loop) {
            System.out.println("show:表示显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:表示添加数据到栈（入栈）");
            System.out.println("pop:表示从栈取出数据（出栈）");
            System.out.println("请输入你的选择：");
            key = sc.next();
            switch (key) {
            case "show":
                stack.list();
                break;
            case "push":
                System.out.println("请输入一个数：");
                int value = sc.nextInt();
                stack.push(value);
                break;
            case "pop":
                try {
                    int res = stack.pop();
                    System.out.printf("出栈的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case "exit":
                sc.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        System.out.println("程序退出~");
    }
}

class ArrayStack {
    private int maxSize;
    private int top;
    private int[] stack;

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

    public boolean isFull() {
        return top == maxSize - 1;
    }

    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 value = stack[top];
        top--;
        return value;
    }

    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]);
        }
    }
}
链表模拟栈
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
public class LinkedListStackDemo {
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        Node node1 = new Node(10);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(40);
        Node node5 = new Node(50);
        System.out.println("入栈~");
        stack.push(node1);
        stack.push(node2);
        stack.push(node3);
        stack.push(node4);
        stack.push(node5);
        stack.list();
        System.out.println("出栈~");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.list();

    }
}

class LinkedListStack {
    Node head = new Node(0);

    public void push(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }

    public int pop() {
        Node temp = head;
        if (temp.next == null) {
            System.out.println("栈空，没有数据~");
        }
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        int value = temp.data;
        temp.pre.next = temp.next;
        return value;
    }

    public void list() {
        if (head.next == null) {
            System.out.println("栈空");
            return;
        }
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class Node {
    public int data;
    public Node next;
    public Node pre;

    public Node(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node [data=" + data + "]";
    }
}
栈实现数学表达式的运算
思路：
  • 通过一个index值（索引），来遍历表达式
  • 如果发现是一个数字，就直接入数栈
  • 如果发现扫描到的是一个符号，就分如下情况：
    • 如果当前符号栈为空，就直接入栈
    • 如果符号栈有操作符，就进行比较
      • 如果当前操作符优先级小于或等于栈中的操作符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果，入数栈。然后将当前操作符入符号栈
      • 如果当前操作符优先级大于栈中的操作符，就直接入符号栈
  • 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
  • 最后在数栈只有一个数字，就是表达式的结果
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
public class Calculator {
    public static void main(String[] args) {
        String expression = "3-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循环的扫描expression
        while (true) {
            // 依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            // 判断ch是什么，然后作相应处理
            if (operStack.isOper(ch)) {
                if (!operStack.isEmpty()) {
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        // 把运算的结果入数栈
                        numStack.push(res);
                        // 然后将当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                } else {
                    // 如果为空直接入栈
                    operStack.push(ch);
                }
            } else {
                // 如果是数，直接入数栈
                // numStack.push(ch-48);
                // 当处理多位数时，不能发现一个数就入数栈，也可能是多位数
                // 在处理数时，需要向expression表达式的index后再看一位，如果是数，继续扫描，如果是符号才入栈
                // 需要定义一个变量，用于拼接

                // 处理多位数
                keepNum += ch;

                // 如果ch已经是expression的最后一位，就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈

                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        // 如果后一位是运算符，则入栈
                        numStack.push(Integer.parseInt(keepNum));
                        // keepNum要清空
                        keepNum = "";
                    }
                }
            }
            // 让index+1，并判断是否扫描到expression最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        while (true) {
            // 如果符号栈为空，则计算到最后的结果，数栈中只有一个数字
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.printf("表达式%s=%d", expression, numStack.pop());
    }
}

class ArrayStack2 {
    private int maxSize;
    private int top;
    private int[] stack;

    public ArrayStack2(int maxSize) {
        top = -1;
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    // 增加一个方法，可以返回当前栈顶的值，但不是pop
    public int peek() {
        return stack[top];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    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 value = stack[top];
        top--;
        return value;
    }

    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 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 = num2 + num1;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num2 * num1;
            break;
        case '/':
            res = num2 / num1;
            break;

        default:
            break;
        }
        return res;
    }
}

前缀表达式（波兰表达式）

  • 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
  • 举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
前缀表达式的计算机求值

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

例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤*如下***:

  • 从右至左扫描，将6、5、4、3压入堆栈
  • 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
  • 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
  • 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

中缀表达式

  • 中缀表达式就是常见的运算表达式，如(3+4)×5-6
  • 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

后缀表达式(逆波兰表达式)

  • 后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
  • 中举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
正常的表达式 逆波兰表达式
a+b a b +
a+(b-c) a b c - +
a+(b-c)*d a b c - d * +
a+d*(b-c) a d b c - * +
a=1+3 a 1 3 + =
后缀表达式的计算机求值

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

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如:

1)从左至右扫描，将3和4压入堆栈；

2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；

3)将5入栈；

4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；

5)将6入栈；

6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果

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
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        // 先定义一个逆波兰表达式
        // (3+4)*5-6-->3 4 + 5 * 6 -
        String suffixExpression = "30 4 + 5 * 6 -";
        // 思路：
        // 先将34+5*6-放到ArrayList中
        // 将ArrayList传递给一个方法，配合栈完成计算
        List<String> rpnList = getListString(suffixExpression);
        int res=calculate(rpnList);
        System.out.println("计算结果是："+res);
    }

    // 将这个逆波兰表达式，依次将数据和运算符放入到ArrayList中
    public static List<String> getListString(String suffixExpression) {
        // 将suffixExpression分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    // 完成对逆波兰表达式的计算
    public static int calculate(List<String> ls) {
        // 创建个栈,只需要一个栈即可
        Stack<String> stack = new Stack<String>();
        for (String item : ls) {
            // 这里使用正则表达式取出数
            if (item.matches("\\d+")) {// 匹配多位数
                stack.push(item);
            } else {
//                pop两个数进行计算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                }else {
                    throw new RuntimeException("运算符有误");
                }
                //把res入栈
                stack.push(res+"");
            }
        }
        //最后留在stack中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}

中缀表达式转后缀表达式

  • 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
  • 从左至右扫描中缀表达式；
  • 遇到操作数时，将其压s2；
  • 遇到运算符时，比较其与s1栈顶运算符的优先级：
    • 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
    • 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
    • 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
  • 遇到括号时：
    • 如果是左括号“(”，则直接压入s1
    • 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左 括号为止，此时将这一对括号丢弃
  • 重复步骤2至5，直到表达式的最右边
  • 将s1中剩余的运算符依次弹出并压入s2
  • 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

举例说明:

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下

因此结果为 “1 2 3 + 4 × + 5 –”

扫描到的元素 s2(栈底->栈顶) s1 (栈底->栈顶) 说明
1 1 空 数字，直接入栈
+ 1 + s1为空，运算符直接入栈
( 1 + ( 左括号，直接入栈
( 1 + ( ( 同上
2 1 2 + ( ( 数字
+ 1 2 + ( ( + s1栈顶为左括号，运算符直接入栈
3 1 2 3 + ( ( + 数字
) 1 2 3 + + ( 右括号，弹出运算符直至遇到左括号
× 1 2 3 + + ( × s1栈顶为左括号，运算符直接入栈
4 1 2 3 + 4 + ( × 数字
) 1 2 3 + 4 × + 右括号，弹出运算符直至遇到左括号
- 1 2 3 + 4 × + - -与+优先级相同，因此弹出+，再压入-
5 1 2 3 + 4 × + 5 - 数字
到达最右端 1 2 3 + 4 × + 5 - 空 s1中剩余的运算符 
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
139
140
141
142
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {

        //完成将一个中缀表达式转后缀表达式的功能
        //1.1+((2+3)*4)-5->转成1 2 3 + 4 * + 5 -
        //2.因为直接对字符串进行操作不方便，因此先将这个字符串转成中缀表达式对应的List
        //3.将得到的中缀表达式对应的List-->后缀表达式对应的List
        String expression="1+((2+3)*4)-5";
        List<String> infixExpressionList=toInfixExpressionList(expression);
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        // 将ArrayList传递给一个方法，配合栈完成计算
        int res=calculate(suffixExpressionList);
        System.out.println(expression+"  -->  "+suffixExpressionList);
        System.out.println("计算结果是："+res);
    }

    //将得到的中缀表达式对应的List-->后缀表达式对应的List
    public static List<String> parseSuffixExpressionList(List<String> ls){
        Stack<String> s1=new Stack<String>();
//        Stack<String> s1=new Stack<String>();
        //说明：因为s2这个栈，在整个转换过程中，没有pop操作，而且后面还需要逆序输出
        //因此比较麻烦，这里直接使用List<String>代替栈
        List<String> s2=new ArrayList<String>();
        for (String item : ls) {
            //如果是一个数，就入数栈
            if (item.matches("\\d+")) {
                s2.add(item);
            }else if (item.equals("(")) {
                s1.push(item);
            }else if (item.equals(")")) {
                while(!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将(弹出s1栈，消除小括号
            }else {
                //当item的优先级小于等于栈顶运算符的优先级，将s1栈顶的运算符弹出并加入s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
                while(s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //还需要将item压入栈
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while(s1.size()!=0) {
            s2.add(s1.pop());
        }
        return s2;//注意因为是存放到List，因此按顺序输出就是对应的后缀表达式对应的List
    }

    //将中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s){
        //定义一个List,存放中缀表达式对应的内容
        List<String> ls=new ArrayList<String>();
        int i=0;//指针，用于遍历中缀表达式字符串
        String str;//对多位数的拼接
        char c;//每遍历一个字符，就放入c
        do {
            //如果c是一个非数字，需要加入到ls
            if ((c=s.charAt(i))<48||(c=s.charAt(i))>57) {
                ls.add(""+c);
                i++;
            }else {//如果是数字，要考虑多位数
                str="";
                while(i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57) {
                    str+=c;
                    i++;
                }
                ls.add(str);
            }
        } while (i<s.length());
        return ls;
    }

    // 完成对逆波兰表达式的计算
    public static int calculate(List<String> ls) {
        // 创建个栈,只需要一个栈即可
        Stack<String> stack = new Stack<String>();
        for (String item : ls) {
            // 这里使用正则表达式取出数
            if (item.matches("\\d+")) {// 匹配多位数
                stack.push(item);
            } else {
//                pop两个数进行计算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                }else {
                    throw new RuntimeException("运算符有误");
                }
                //把res入栈
                stack.push(res+"");
            }
        }
        //最后留在stack中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}

//编写一个类Operation，可以返回一个运算符对应的优先级
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;

    //写一个方法，返回对应的优先级数字
    public static int getValue(String operation) {
        int result=0;
        switch (operation) {
        case "+":
            result=ADD;
            break;
        case "-":
            result=SUB;
            break;
        case "*":
            result=MUL;
            break;
        case "/":
            result=DIV;
            break;
        default:
            System.out.println("不存在该运算符");
            break;
        }
        return result;
    }
}