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

定义

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

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。

负责车厢调度的工作人员需要知道能否使它以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));
    }
}