946. Verify stack sequence

946. Verify stack sequence

Given  pushed  and  popped  Two sequences , In each sequence   The values are not repeated , Only if they could have been pushed on the original empty stack push And pop up pop When manipulating the result of a sequence , return  true; otherwise , return  false .

Example 1：

 Input ：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
 Output ：true
 explain ： We can do it in the following order ：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2：

 Input ：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
 Output ：false
 explain ：1  Can't be in  2  Pop up before .

Tips ：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed  All elements of   Different from each other
• popped.length == pushed.length
• popped  yes  pushed  An arrangement of

---

Our approach is to stack the stack sequence first , When the out of stack sequence is the same as the in stack sequence , The elements at the top of the stack should be out of the stack , At the same time, the stack sequence then traverses the next element

This is the same situation ：

  This is a different situation ：

  Ideas ：

Let the stack queue stack one by one , See whether the top element of the stack is the same as the out of stack queue element , If it's not the same , Let the stack queue stack one by one , If it is the same, let the top element out of the stack , At the same time, the stack queue traverses the next element , Continue reciprocating cycle , Finally, if the stack array traversal is completed and the stack is empty, it proves that the stack queue is the same as the stack queue , If the last stack array traversal is completed and the stack is not empty , That proves that the stack in queue is different from the stack out queue .

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> s = new Stack<Integer>();
        int index = 0;
        for(int i = 0 ; i < pushed.length; i ++){
            s.push(pushed[i]);// Push the stack sequence onto the stack 
            while(!s.isEmpty() && index<popped.length&&popped[index] == s.peek()){
                // When the stack is not empty and index Do not cross the boundary to see whether the stack sequence is the same as the top element 
                s.pop();// If the same pop-up stack top element 
                index++;// Traverse the next element 
            }
        }
        return s.isEmpty();
    }
}