luffy博客

栈

5/25/2023 data-structure

# 栈

# 1、栈的概念

# Ⅰ-什么是栈

  • 栈的英文为(stack)

  • 栈是一个先入后出(FILO-First In Last Out)的有序列表。

  • 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的 一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

  • 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

  • 图解方式说明出栈(pop)和入栈(push)的概念

# Ⅱ-栈的应用场景

栈作为一种重要的基本数据结构，它的应用是比较广泛的。栈的应用包括如下几个方面：

  • 子程序的调用：在跳往子程序前， 会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出， 以 回到原来的程序中；

  • 处理递归调用：和子程序的调用类似， 只是除了储存下一个指令的地址外， 也将参数、 区域变量等数据存入堆 栈中；

  • 表达式的转换（中缀表达式转后缀表达式）与求值；

  • 二叉树的遍历；

  • 图形的深度优先（depth 一 first）搜索法。

# 2、数组模拟栈

由于栈是一种有序列表， 当然可以使用数组的结构来储存栈的数据内容。下面我们就用数组模拟栈的出栈， 入栈等操作。

# Ⅰ-思路分析

使用数组来模拟栈的思路是比较简单的，按照下面的步骤即可

  • 定义一个类，该类的成员变量包括一个数组 stack（用于模拟栈）、两个整型变量 maxSize、top（分别代表栈的大小、栈顶指针）；

  • 栈顶指针 top 初始化为 -1；

  • 每当有元素要入栈时，top 加 1，然后元素记录在数组中，即 stack[top] = element；

  • 每当有元素要出栈时，先读取数组的元素，即 element = stack[top]，然后 top 减 1。

# Ⅱ-代码实现

package com.stack;
import java.util.Scanner;
public class ArrayStackDemo {
   public static void main(String[] args) {
       //测试一下ArrayStack 是否正确
       //先创建一个ArrayStack对象->表示栈
       ArrayStack stack = new ArrayStack(4);
       String key = "";
       boolean loop = true; //控制是否退出菜单
       Scanner scanner = 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 = scanner.next();
           switch (key) {
               case "show":
                   stack.list();
                   break;
               case "push":
                   System.out.println("请输入一个数");
                   int value = scanner.nextInt();
                   stack.push(value);
                   break;
               case "pop":
                   try {
                       int res = stack.pop();
                       System.out.printf("出栈的数据是 %d\n", res);
                   } catch (Exception e) {
                       // TODO: handle exception
                       System.out.println(e.getMessage());
                   }
                   break;
               case "exit":
                   scanner.close();
                   loop = false;
                   break;
               default:
                   break;
           }
       }

       System.out.println("程序退出~~~");
   }
}

//1. 定义一个ArrayStack栈
class ArrayStack {
   private int maxSize;//栈的大小
   private int[] stack; //数组,数组模拟栈
   private int top = -1; //top表示栈顶,初始化为-1

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

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

   //栈空
   public boolean isEmpty() {
       return top == -1;
   }

   //入栈--push
   public void push(int value) {
       if (isFull()) {
           System.out.println("栈满");
           return;
       }
       top++;
       stack[top] = value;
   }

   //出栈-pop,将栈顶的数据返回
   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
88
89
90
91
92
93
94
95
96
97
98
99
100
101

# 3、栈实现简单计算器（中缀）

# Ⅰ-思路分析

  1. 表达式分为中缀表达式、前缀表达式、后缀表达式。中缀表达式就是表达式本身，如 “3+2*6-1” 就是一个中缀表达式。关于表达式的详细介绍将会在后面的笔记中展示

  2. 本案例实现的简单计算器就是直接对中缀表达式（也就是原计算表达式）进行分析处理。

  3. 如果要实现一个计算器，可以按照以下思路：

    • 初始化两个栈，一个作为符号栈、一个作为数字栈；

    • 通过一个索引 index，来从左至右遍历中缀表达式；

    • 如果遍历到的是一个数字，就直接入数字栈；

    • 如果遍历到的是一个符号：

    ① 如果当前符号栈为空，就直接入符号栈；

    ② 如果符号栈有操作符，就进行比较：

    1. 若当前的操作符优先级小于或等于栈顶的操作符，就从数字栈中 pop 出两个数，再从符号栈中 pop 出一个符号进行运算。运算得到的结果 push 入数字栈中，然后将当前的操作符入符号栈；
    2. 若当前的操作符优先级大于栈顶的操作符，就直接入符号栈；

    • 中缀表达式遍历完毕之后，就依次从数字栈和符号栈中 pop 出相应的数和符号，对他们进行运算；

    • 最后在数字栈中将只剩下一个数字，这个数字就是表达式的结果。

  4. 思路分析图:

# Ⅱ-代码实现:

package com.luffe.stack;

public class Calculator {
   public static void main(String[] args) {
       String expression = "70*2+2*3+2000";
       //先创建两个栈,一个数栈一个符号栈
       ArrayStack2 numStack = new ArrayStack2(10);
       ArrayStack2 operStack = new ArrayStack2(10);
       //定义相关变量
       int index = 0, num1 = 0, num2 = 0, oper = 0, res = 0;
       char ch = ' ';//每次将扫描到的char保存于ch中
       String keepNum = "";//用于拼接多位数
       //开始循环扫描expression
       while (true) {
           //依次得到expression的每一个字符
           ch = expression.substring(index, index + 1).charAt(0);
           //判断ch是什么
           if (operStack.isOper(ch)) {//如果是运算符
               if (!operStack.isEmpty()) {//判断当前字符站是否为空
                   //如果符号栈中有操作符,就进行比较如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数
                   //再从符号栈中pop出一个符号进行运算,再将得到的结果入数栈,然后将当前的操作符入符号栈
                   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); //? "1+3" '1' => 1
               //分析思路
               //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
               //2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
               //3. 因此我们需要定义一个变量 字符串，用于拼接
               //处理多位数
               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 = "";
                   }
               }
           }
           index++;
           if (index >= expression.length()) break; //结束循环，跳出循环体，执行后面的程序。
       }
       //当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并进行运算
       //经过上面的操作，符号栈剩下的都是优先级相等的符号了，直接出栈做运算就可以啦
       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.println("-------- 出循环后数栈 ---------");
//            numStack.list();
//            System.out.println("-----------------");
       }
       int res2 = numStack.pop();
       System.out.printf("表达式%s=%d", expression, res2);
   }
}


//1. 定义一个ArrayStack栈
class ArrayStack2 {
   private int maxSize;//栈的大小
   private int[] stack; //数组,数组模拟栈
   private int top = -1; //top表示栈顶,初始化为-1

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

   //可以返回当前栈顶的值,但不是pop,而是用做对比
   public int peek() {
       return stack[top];
   }

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

   //栈空
   public boolean isEmpty() {
       return top == -1;
   }

   //入栈--push
   public void push(int value) {
       if (isFull()) {
           System.out.println("栈满");
           return;
       }
       top++;
       stack[top] = value;
   }

   //出栈-pop,将栈顶的数据返回
   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 = num1 + num2;
               break;
           case '-':
               res = num2 - num1;// 注意顺序
               break;
           case '*':
               res = num1 * num2;
               break;
           case '/':
               res = num2 / num1;
               break;
           default:
               break;
       }
       return res;
   }
}
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

# 4、前缀、中缀、后缀表达式

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

  1. 概念

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。

  1. 案例

    (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

  2. 前缀表达式的计算机求值

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

  • Demo：（3+4)_5-6 对应的前缀表达式就是 - + 3 4 5 6，针对前缀表达式求值步骤如下：

（1）从右至左扫描，将 6、5、4、3 压入堆栈

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

（3）接下来是 × 运算符，因此弹出 7 和 5，计算出 7×5=35，将 35 入栈

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

# 中缀表达式

  1. 概念

中缀表达式就是常见的运算表达式，即运算符在操作数之间。

  1. 中缀表达式的计算机求值

中缀表达式是人们最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其他表达式来操作（一般转成后缀表达式） 3 + 4 * 5 - 6

# 后缀表达式

  1. 概念

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

  1. 案例

(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

  1. 前缀表达式的计算机求值

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

  • Demo：(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，由此得出最终结果

# 5、后缀表达式(逆波兰表达式)计算实现

1.思路分析

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

  2. 遇到+运算符，因此弹出 4 和 3 (4 为栈顶元素，3 为次顶元素》，计算出 3+4 的值，得 7，再将 7 入栈;

  3. 将 5 入栈;

  4. 接下来是 x 运算符，因此弹出 5 和 7，计算出 7x5=35，将 35 入栈;

  5. 将 6 入栈;

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

2.代码实现

package com.luffy.stack;

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

/**
 * @author dreamLuffe
 * @data 2023/5/23 10:12
 */
public class PolandNotation {
    public static void main(String[] args) {
        //先定义一个逆波兰表达式
        //(30+4)x5-6 => 30 4 +5 X 6 -  => 164
        String suffixExpression = "30 4 + 5 * 6 -";
        //思路
        //1。先将“3 4+5x 6-"=>放到ArrayList中//
        // 2。将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
        List<String> rpnList = getListString(suffixExpression);
        System.out.println("rpnList" + rpnList);

        int res = calculate(rpnList);
        System.out.println("计算结果："+res);
    }

    /**
     * 将一个逆波兰表达式，一次将数据何运算法存放List
     *
     * @param suffixExpression
     * @return
     */
    public static List<String> getListString(String suffixExpression) {
        //分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        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 {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num2 + num1;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push("" + res);
            }
        }
        return  Integer.parseInt(stack.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

# 6、 中缀表达式转后缀表达式

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式

具体步骤如下 初始化两个栈:运算符栈s1和储存中间结果的栈s2: 从左至右扫描中缀表达式; 遇到操作数时，将其压s2; 遇到运算符时，比较其与s1栈顶运算符的优先级: 如果s1为空，或栈顶运算符为左括号“1”，则直接将此运算符入栈:(2) 否则，若优先级比栈顶运算符的高，也将运算符压入s1:(3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较;

Last Updated: 11/10/2023, 11:47:31 PM

串