题目描述

原题链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

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

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

解题思路

K 神题解：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

• 建立一个辅助栈来实现给定的 push 和 pop 操作，push 一个元素的同时，假如遇到了 pop 相同元素，则进行 pop 操作，最后辅助栈中如果为空，表示给的 push 和 pop 序列是正确的：能够全部 push 进去，也能全部 pop 出来。

• 简言之，就是建立一个辅助栈来模拟入栈和出栈，如果入栈和出栈的序列都被执行了，那么此时的栈是为空的。

• 第7行的 while 循环是用来判断当前入栈的值和 poped[i] 的值相等时，入栈的值被弹出，i++，继续循环判断之前入栈的值是否与poped[i] 相等。比如入栈序列是 1>2>3>4>5 而出栈序列是 5>4>3>2>1 那么显而易见的，前4次入栈都不会与出栈序列的第一个值相等，不会执行出栈，而当入栈5时，它就和出栈序列的第一个元素相等，5出栈，此时 i++ 出栈序列的第一个元素变为 4，由于入栈的 5 被弹出了，此时的 stack.peek 的值就是 4 ，相等，继续被弹出！直到全部被弹出！卧槽，有点难理解！

• 重点是第7行代码的 stack.peek( ) 它会循环探测当前在栈中的栈顶元素是否和出栈序列的当前元素相等，如果相等的话，循环体就弹出栈顶的元素，并且此时 stack.peek( ) 的值会更新！所以循环才得以继续进行！

  class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
  }