输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
package JianZhiOffer; import java.util.Stack; /** * 1.首先new一个栈，让元素按顺序入栈 * 2.将入栈的元素与出栈数组元素按顺序一一比较，如果相等，则说明此时该元素入栈后立即出栈，则说明有一个元素出栈，那么将记录出栈个数的j加1；并且将该元素弹出栈，此时如果是入栈一个就立即弹出一个，则记录出栈个数的j会在最后一个元素出栈时达到数组长度-1（即全部出栈），则说明是正确的出栈顺序（例如：入栈顺序： 1，2，3，4，5，6，7，8，出栈顺序为1，2，3，4，5，6，7，8，），如果不是入栈一个元素就立即出栈一个元素，那么临时栈中的元素不会全部弹出，所以需要到下一个while循环继续判断剩下的是否为正确的出栈顺序。 * * @author xieliang * */ public class IsPopOrder { public static boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length<=0||popA.length<=0) return false; int j=0; Stack<Integer> s=new Stack<Integer>(); for(int i=0;i<pushA.length;i++) { s.push(pushA[i]); if(pushA[i]==popA[j]) { if(j++==pushA.length-1) return true; s.pop(); } } while(!s.isEmpty()) { if(popA[j++]!=s.pop()) return false; } return true; } public static void main(String[] args) { int[] pushA={1,2,3,4,5,6,7,8}; int[] popA1={1,2,3,4,5,6,7,8}; int[] popA2={7,8,6,5,4,3,2,1}; int[] popA3={5,6,7,8,4,2,3,1}; boolean result1=IsPopOrder(pushA,popA1); boolean result2=IsPopOrder(pushA,popA2); boolean result3=IsPopOrder(pushA,popA3); System.out.println(result1+" "+result2+" "+result3); } }
运行结果：true true false
