Determine whether a sequence is a stack pop-up sequence

One , Title Description

Enter two sequences of integers , The first sequence represents the push order of the stack , Please determine if the second sequence is likely to be the pop-up sequence of the stack . Suppose that all the Numbers pushed are not equal . For example, the sequence 1,2,3,4,5 Is the push order of a stack , Sequence 4,5,3,2,1 Is a popup sequence corresponding to the stack sequence , but 4,3,5,1,2 It cannot be a popup sequence of the push sequence .（ Be careful ： The lengths of the two sequences are equal ）

Two , Topic analysis

The two sequences given in question , One is the stack sequence , One is the stack sequence .
In the case of ensuring the order of the stack sequence , The alternate order of entering and leaving the stack , A sequence that causes the stack sequence to have a different order .

Their thinking ：

• 1. If one of the popup sequence is empty , Go straight back to false
• 2. Use an auxiliary stack to save the stack sequence , A tag variable to locate the element position of the pop-up sequence
• 3. Loop stack , In the outer circle （ Traverse the stack sequence ）, Recycling comparison （while）, If s The stack is not empty and the top element of the stack is equal to the pop-up sequence popIndex position , Keep coming out of the stack
• 4, Finally, if the auxiliary stack is empty , It means that it is a return of the stack out method of the stack sequence true, If it is not empty, it is not , Go straight back to false

3、 ... and , Code up （ Read notes ！！！）

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    
        if(pushA.length == 0 || popA.length == 0){
     // If one of the popup sequence is empty 
            return false;
        }
        Stack<Integer> s = new Stack<>(); // Used to organize elements that pop into the sequence 
        int popIndex = 0; // The position of the element in the sequence used to mark the position of the pop-up 
        for(int i = 0; i < pushA.length;i++){
    
            // Loop through the popup sequence , Put on the stack in turn s
            s.push(pushA[i]);
            while(!s.isEmpty() && s.peek() == popA[popIndex]){
    
                // If s The stack is not empty and the top element of the stack is equal to the pop-up sequence popIndex position 
                // Here the loop is the core , Determine whether it is one of many stack order 
                // Out of the stack 
                s.pop();
                //pop Bit backward 
                popIndex++;
            }
        }
        // The loop ends , If the stack s It's empty , It means that it is a pop-up sequence of the stack sequence 
        return s.isEmpty();
    }
}