【Java 数据结构】栈与OJ题

风在叙述它的阅历，树在书写它的温柔。

目录

风在叙述它的阅历，树在书写它的温柔。

1、什么是栈？

2、模拟实现一个栈

2.1 构造方法和成员属性

2.2 push 方法

2.3 pop 方法

2.4 peek 方法

2.5 empty 方法

3. 栈相关的OJ题

3.1 有效括号(来源:LeetCode 难度:简单)  

3.2 逆波兰表达式求值(来源:LeetCode 难度:中等)  

3.3 栈的压入、弹出序列(来源:牛客网 难度:中等) 

---

1、什么是栈？

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 详细介绍请查看博主C语言实现数据结构专栏！

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

---

2、模拟实现一个栈

2.1 构造方法和成员属性

public class MyStack {
    private int[] elem; //存放数据的数组
    private int size; //有效元素个数
    private static final int DEFAULT_CAPACITY = 10; //约定好的默认容量
 
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
        this.size = 0;
    }
}

有了顺序表和链表的学习，再次学习栈是很轻松的，但是在源码中，开辟空间是在 push 中开辟的，跟顺序表类似的。

2.2 push 方法

// 压栈
public int push(int data) {
    // 判断是否需要增容
    if (this.size == this.elem.length) {
        this.elem = Arrays.copyOf(this.elem, this.size * 2);
    }
    // 压栈只能往栈顶压栈
    this.elem[this.size++] = data;
    return data;
}

在实现push方法要注意，栈扩容的问题，因为我们底层使用的是数组，所以可以用 Arrays.copyOf方法进行扩容。 

2.3 pop 方法

// 出栈
public int pop() {
    // 判断栈是否为null
    if (this.size == 0) {
        throw new MyStackEmptyException("栈为空！");// 自定义异常
    }
    return this.elem[--this.size];
}

在出栈方法中，如果栈为null的情况是不能进行出栈的，也就是有效元素个数size为0的情况，这里博主是直接抛出了一个自定义异常。在返回值的地方也要注意，出栈后栈的元素会减少一个，但我们只需要设置有效数据减一个即可，就像计算机中的删除一样，本质是将数据设置成无效，有新的数据可以直接覆盖。

2.4 peek 方法

// 查看栈顶元素
public int peek() {
    // 判断栈是否为null
    if (this.size == 0) {
        throw new MyStackEmptyException("栈为空！"); //自定义异常
    }
    return this.elem[this.size - 1];
}

peek方法与pop方法相差无几，需要注意的是在返回栈顶元素的时候不要使有效数据个数减少了就像。

2.5 empty 方法

// 判断栈是否为空
public boolean empty() {
    return this.size == 0;
}

---

3. 栈相关的OJ题

3.1 有效括号(来源:LeetCode 难度:简单)  

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

解题思路：这道题我们可以利用本期学到的栈，由于栈先进后出的特性，我们可以遍历这个字符串，如果是左括号就入栈，右括号就出栈进行判断是否匹配，但是在这个过程中，如果字符串遍历时碰到了右括号，但是栈空了，则不匹配，当字符串遍历完成了，栈还有元素，表示左括号多于右括号，也不匹配，只有遍历完了这个字符串，栈也空了，此时才是匹配的！

class Solution {
 
    public boolean isLeftBracket(char ch) {
        return ch == '(' || ch == '{' || ch == '[';
    }
 
    public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        Stack stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 如果为左括号
            if (isLeftBracket(ch)) {
                stack.push(ch); //为左括号就入栈
            } else if (!stack.empty()) {
                char left = stack.pop();
                // 如果括号不匹配
                if (!((left == '(' && ch == ')') || (left == '{' && ch == '}') || (left == '[' && ch == ']'))) {
                    return false;
                }
            } else { //走到这表示栈为null,还是右括号需要出栈的情况
                return false;
            }
        }
        if (stack.empty()) {
            return true;
        } else { //走到这，表示栈中剩余了左括号,也就是左括号比右括号多
            return false;
        }
    }
}

3.2 逆波兰表达式求值(来源:LeetCode 难度:中等)  

题目：根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

解题思路：在做这道题之前，我们要看清楚题目的示例，什么是逆波兰表达式，小伙伴们可以去网上查阅下，那么这道题的思路可以如何做呢？也可以使用栈来做，如果碰到数字字符我们就转换成整数入栈，如果碰到的是+-*/这些运算符我们就出栈顶两个元素，第一个做右操作数，第二个做左操作数，为什么第一个取出的元素是右操作数呢？因为如果是 2 1 /，这样我们要转换成 2 / 1，因为栈是后进先出的，如果把第一个作为左操作数就是 1 / 2，那么结果就完全变了。当然我们出栈还得判断栈是否为null的情况，出栈两个元素完成后，匹配对应的操作符进行运算，接着把算出的结果入栈，直到遍历完题目给的数组，此时的栈顶元素就是逆波兰表达式的结果。代码如下：

class Solution {
 
    public boolean isOperator(String s) {
        return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));
    }
    public int evalRPN(String[] tokens) {
        if (tokens == null) {
            return -1;
        }
        Stack stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String tmp = tokens[i];
            int right = 0;
            int left = 0;
            // 如果i下标的位置不是+-*/
            if (!isOperator(tmp)) { 
                stack.push(Integer.parseInt(tmp)); //把数字字符转换成整型入栈
            } else if (stack.size() >= 2){ //至少有两个元素
                // i下标为操作符的情况下，出栈顶两个元素
                right = stack.pop();
                left = stack.pop();
                switch(tmp) {
                    case "+" :
                        stack.push(left + right);
                        break;
                    case "-" :
                        stack.push(left - right);
                        break;
                    case "*" :
                        stack.push(left * right);
                        break;
                    case "/" :
                        stack.push(left / right);
                        break;
                }
            } else { // 如果碰到了操作符，栈不满足2个元素的条件下，证明这个逆波兰表达式不成立
                return -1;
            }
        }
        return stack.pop(); //栈顶元素就是最终的值
    }
}

3.3 栈的压入、弹出序列(来源:牛客网 难度:中等) 

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同 

解题思路：这个题相较于前两道题还是比较简单的，我们可以定义i，j变量分别为入栈数组下标和出栈数组的下标，先入栈，如果此时栈顶元素等于出栈数组 j 下标的元素则出栈，j++循环，当 i 遍历完了入栈数组，结束了循环，如果栈为null了，表示是匹配的序列，不为null则不匹配。代码如下：

public class Solution {
    
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA == null || popA == null) {
            return false;
        }
        Stack stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            // 如果此时栈顶元素于popA j下标位置元素相等
            while (!stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        if (stack.empty()) {
            return true;
        } else {
            return false;
        }
    }
}

---

下期预告：【Java 数据结构】队列与OJ题