[java-アルゴリズム-データ構造]スタックのポップアップ順序が正しいかどうかを判断する


package stack;

import java.util.Hashtable;
import java.util.Stack;

/**
 *         ,             ,                  。
 *               。    1,2,3,4,5        ,  4,5,3,2,1               ,
 *  4,3,5,1,2               。(  :            )
 * Created by ZeHua on 2017/5/15.
 */
public class IsPopOrder {
    //               ,     
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length!=popA.length)return false;
        if(popA.length==1&&popA[0]!=pushA[0]){
            return false;
        }else if(popA.length==1&&popA[0]==pushA[0]){
            return true;
        }
        //      
        Hashtable value_index = new Hashtable<>();
        for(int i=0;i//     ——       
            value_index.put(pushA[i],i);
        }

        //       ,       
        Stack max_index = new Stack<>();
        //     pushA  
        int end_index = 0;

        //    ,         ,                  
        for(int i=0;i//  popA[i]   pushA   
            int cur_index_popAinPushA  = value_index.get(popA[i]);

//            int top_maxStack=max_index.peek();
            //              ,   
            if(max_index.isEmpty()||cur_index_popAinPushA>max_index.peek()){
                for(int j=end_index;j<=cur_index_popAinPushA;j++){
                    max_index.push(j);
                }
                end_index= max_index.pop()+1;
                continue;
            }
            //          ,   
            if(cur_index_popAinPushA==max_index.peek()){
                max_index.pop();
                continue;
            }


            if(cur_index_popAinPushA//          ,         
                return false;
            }
        }

        //      ,  true
        return true;
    }
}