这个这个……之前学数据结构的时候也遇到过,甚至想起红色算法第四版的课后习题也有这个,但就是没有去实现它,自己模拟模拟倒是很容易模拟出来,但写成代码就……之前是不想写(其实应该是不会写),现在…依旧。
要怎么做呢,其实就是把步骤变成代码,只要你能正确地判断,就可以写出代码来。

以示例1为例,给定输入的序列【1,2,3,4,5】,判断序列【4,5,3,2,1】是否合法。下面的步骤可能很冗余,但看一遍之后,再联想一下如何写代码,应该是很清晰的。
很明显,我们应该使用一个栈来模拟进栈出栈的情况。

  1. 入栈【5】。栈:【5】
  2. 判断序列首元素,是【4】,不合要求。栈:【5】
  3. 入栈【4】。栈:【5,4】
  4. 判断序列,是【4】,合要求,【4】出栈。栈:【5】
  5. 判断序列,是【5】,合要求,【5】出栈。栈:【 】
  6. 入栈【3】。栈:【3】
  7. 判断序列,是【3】,合要求,【3】出栈。栈:【 】
  8. 入栈【2】。栈:【2】
  9. 判断序列,是【2】,合要求,【2】出栈。栈:【 】
  10. 入栈【1】。栈【1】
  11. 判断序列,是【1】,合要求,【1】出栈。栈:【 】
  12. 所有元素已经入栈,且序列所有元素都合要求,说明该序列合法,返回true。

文字总是枯燥的,自己画画,也会得到相同的结果。
在代码上,首先是让元素逐一入栈,然后判断栈的元素是否与给出序列相同(注意这里可以进行多次判断,是个循环),若相同的话就让栈中的元素出栈。这样一直判断下去,最终查看一下栈是否为空(栈不为空说明有不合要求的序列,不然应该全部都出栈了),返回结果。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;
        for(int i = 0;i < pushed.length;i++){
            // 利用循环将要进栈的元素加入到栈中
            stack.push(pushed[i]);
            // 模拟出栈操作,如果能顺利出栈,则代表这个结点的结果是正确的
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
        // 如果最后栈中还有元素的话,说明序列不正确
        return stack.isEmpty();
    }
}