出栈序列【模拟】

叁歲伎倆 2022-11-27 07:23 131阅读 0赞

判断给定序列是否为某一序列的出栈序列。

注意：不必求出全部的出栈序列。

//import java.util.Collection;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class OutStack {
        public static void main(String[] args) {
            String A = new Scanner(System.in).next();
            String B = new Scanner(System.in).next();
            boolean flag=isPopSerial2(A,B);
            if (flag){
                System.out.println(B+"是"+A+"的一种出栈序列");
            }else {
                System.out.println(B+"不是"+A+"的一种出栈序列");
            }
        }
    
        public static boolean isPopSerial2(String A,String B){
            Stack<Character> stack = new Stack<>();
    
            if (A==null||B==null) return false;
    
            int ALen=A.length(),BLen=B.length();
            if (ALen!=BLen) return false;
    
            int BIndex=0,AIndex=0;
    
            while (AIndex<ALen){
                stack.push(A.charAt(AIndex));
                AIndex++;
                while (!stack.isEmpty() && B.charAt(BIndex)==stack.peek()){  //注意判空！！
                    stack.pop();
                    BIndex++;
                }
            }
            return BIndex==BLen;
        }
    
    /*    public static boolean isPopSerial(String A,String B){
            Stack<Character> stk=null;
            String[] col=new String[A.length()];
            int cnt=0;
    
            for(int i=0;i<A.length();i++){
                stk.push(A.charAt(i));
    
                char temp=stk.pop();
                col[cnt]+=temp;
                if(col[cnt].length()==B.length()){
                    if(col[cnt]==B) return true;
                    else cnt++;
                }
                stk.push(temp);
            }
            return false;
        }*/
    
    }