给定压栈顺序,判断出栈顺序是否合法
栈的压入、弹出序列
http://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
给出压栈顺序,判断出栈顺序是否合理。
维护一个栈,循环遍历出栈顺序,当第i个和栈顶相等时,栈顶弹出,否则进行压栈。
当全部都压栈完了之后,栈顶还是和第i个出栈顺序不同,则不合法。如果能循环完,则是合法的。
注意栈空的时候 peek会抛异常。
import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { int l1 = pushA.length; int l2 = popA.length; Stack<Integer> stack = new Stack<>(); int pushIndex = 0; for(int i=0;i<l2;i++){ int tx = popA[i]; while(pushIndex==0||stack.peek()!=tx){ if(pushIndex>=l1){ return false; } stack.push(pushA[pushIndex]); pushIndex++; } stack.pop(); } return true; } }