Java面试知识点（六十七）数据结构之栈

╰+哭是因爲堅強的太久メ 2021-09-20 18:42 396阅读 0赞

### 定义 ###

栈是只能在某一端插入和删除的特殊线性表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

--------------------

### java中的栈 ###

java有现成的工具类Stack

import java.util.Stack;

工具类Stack提供了几个现成的操作栈的方法

*  push() 压栈，向栈顶存入一个元素
 *  pop() 弹栈，从栈顶取出一个元素，并返回该元素
 *  peek() 返回栈顶的元素，但是并不取出
 *  empty() 判断栈是否为空

--------------------

### 栈的实例 ###

**【例1】括号的匹配（表达式的合法性检查）**

【问题描述】  
假设一个表达式有英文字母（小写）、运算符（+，—，\*，/）和左右小（圆）括号构成。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“true”；否则返回“false”。假设表达式长度小于255，左圆括号少于20个。

【代码示例】

package base.datastructure.stack;
    
    import java.util.Scanner;
    import java.util.Stack;
    
    public class Brackets { 
        /** * 括号匹配，使用辅助结构——栈 * 从左向右扫描，遇到左括号压栈，遇到右括号弹栈 * 成功——扫描完毕，堆栈为空 * 失败—— * 1.左括号多余右括号，扫描完毕，不为空； * 2.右括号多余左括号，弹栈失败； * 3.左右括号一样多，但是右括号在左括号前面，弹栈失败； * */
        public boolean method(String str) { 
            char[] chars = str.toCharArray();
            Stack<Character> stack = new Stack<>();
            for (Character a : chars) { 
                if (a.equals('(')) { 
                    stack.push('(');
                }
                if (a.equals(')')) { 
                    if (stack.empty()) { 
                        return false;
                    } else { 
                        stack.pop();
                    }
                }
            }
            if (stack.empty()) { 
                return true;
            } else { 
                return false;
            }
        }
    
        public static void main(String[] args) { 
            // String str = "";
            Scanner scan = new Scanner(System.in);
            String str = scan.next();
            Brackets brackets = new Brackets();
            System.out.println(brackets.method(str));
        }
    }

--------------------

**【例2】编程求一个后缀表达式的值**

【问题描述】  
从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（.）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。

【算法分析】  
后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。  
比如，16–9\*(4+3)转换成后缀表达式为：  
16□9□4□3□+\*–，

【代码示例】

package base.datastructure.stack;
    
    import java.util.Scanner;
    import java.util.Stack;
    
    public class Suffix { 
        /** * 后缀表达式， * 遇到数字压栈，遇到符号把栈顶的两个元素拿出来，进行计算 * 计算之后，把结果再次压栈，最后的结果就是最终结果 * * 如何把字符串转换为int类型： * 1. 使用String的valueOf() * int num = Integer.parseInt(String.valueOf(a)); * 2. 使用ascii码(仅限于char类型) * int num = (int)a - (int)'0'; * */
        public int method(String str) { 
            String[] ss = str.split(" ");
            Stack<String> stack = new Stack<>();
            for (String s : ss) { 
                switch (s) { 
                    case "+" :
                        String s11 = stack.pop();
                        String s12 = stack.pop();
                        int i11 = Integer.parseInt(String.valueOf(s11));
                        int i12 = Integer.parseInt(String.valueOf(s12));
                        int i1 = i11 + i12;
                        stack.push(i1+"");
                        break;
                    case "-" :
                        String s21 = stack.pop();
                        String s22 = stack.pop();
                        int i21 = Integer.parseInt(String.valueOf(s21));
                        int i22 = Integer.parseInt(String.valueOf(s22));
                        int i2 = i22 - i21;
                        stack.push(i2+"");
                        break;
                    case "*" :
                        String s31 = stack.pop();
                        String s32 = stack.pop();
                        int i31 = Integer.parseInt(String.valueOf(s31));
                        int i32 = Integer.parseInt(String.valueOf(s32));
                        int i3 = i31 * i32;
                        stack.push(i3+"");
                        break;
                    case "/" :
                        String s41 = stack.pop();
                        String s42 = stack.pop();
                        int i41 = Integer.parseInt(String.valueOf(s41));
                        int i42 = Integer.parseInt(String.valueOf(s42));
                        int i4 = i42 / i41;
                        stack.push(i4+"");
                        break;
                    default :
                        stack.push(s);
                }
            }
            if (stack.empty()) { 
                return 0;
            }
            return Integer.parseInt(String.valueOf(stack.pop()));
        }
    
        public static void main(String[] args) { 
            String str = "16 9 4 3 + * -";
            Suffix suffix = new Suffix();
            System.out.println(suffix.method(str));
        }
    }

--------------------

**【问题描述】**  
有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]  
负责车厢调度的工作人员需要知道能否使它以a1,a2,…,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。

**【输入】**  
输入文件的第一行为一个整数n，其中n<=1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。

**【输出】**  
如果可以得到指定的车厢顺序，则输出一个字符串  
”YES”，否则输出”NO”（注意要大写，不包含引号）。

**【输入样例】**  
5  
5 4 3 2 1

**【输出样例】**  
YES

**【代码示例】**

package base.datastructure.stack;
    
    import java.util.Stack;
    
    public class Car { 
        /** * 车厢调度 * 驶入序号A，数组，需要一个游标记录进入C的最大车号 * 驶出序号B，目标数组，需要判断是否正确 * 中转序号C，存储栈， * * 思路：遍历给定目标数组，设定一个游标，初始值为0， * 如果游标小于数组值，则 * 把游标到给定数组之间的数字全部存入栈中，同时弹栈一次 * 如果游标大于数组值，则 * 弹栈一次，并比较当前数组跟弹出的值，不同则错误，相同继续 * 遍历完成之后，栈为空，正确 * */
        public String method(int[] cars) { 
            int n = cars.length;
            Stack<Integer> stack = new Stack<>();
            // 定位的游标
            int flag = 0;
            for (int i=0; i<n; i++) { 
                if (cars[i] > flag) { 
                    // 当游标跟车号一致跳出,此时一致的车号也加入栈中
                    while (flag < cars[i]) { 
                        flag ++;
                        stack.push(flag);
                    }
                    // 弹栈一次，为了进行比对车号
                    stack.pop();
                } else { 
                    int car = stack.pop();
                    if (car != cars[i]) { 
                        return "NO";
                    }
                }
            }
            if (stack.empty()) { 
                return "YES";
            }
            return "NO";
        }
    
        public static void main(String[] args) { 
            int[] a = { 1,2,5,3,4};
            System.out.println(new Car().method(a));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/1e5a57916fe947bbb114ec5c51986827.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/bcdfaa78307d464eaa646677f470c853.png