[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;
}
}