判断出栈顺序是否正确(栈的压入、弹出序列)

输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。

　　比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

 

直接上代码，共有两种方法。

package test;
import java.util.Stack;
public class StackPopSeq {/*** 根据数字排列特性* 若a[i+1] > a[i]，则a[i+1] 大于前面所有的数* 即，如果按小到大出来的数，必定是进去就出来，那么比它们还大的数，就不可能比他们还早出来* @param a* @return*/private static boolean isPopSeqByNO(int[] a) {boolean flag = true;int max = a[0];for(int i=1;i){if(a[i-1]max){flag = false;break;}max = Math.max(Math.max(a[i-1],a[i]),max);}return flag;
}/*** 通过模拟栈的进出进行判断，* 先for循环把arr1中的元素入栈，并在每次遍历时，检索arr2中可以pop的元素。* 如果循环结束，而stack中还有元素，就说明arr2序列不是pop序列。* @param a1* @param a2* @return*/private static boolean isPopSeqBySimulate(int[] a1, int[] a2) {// TODO Auto-generated method stub
    Stack s = new Stack();for(int i=0,j=0;i){s.push(a1[i]);while(!s.empty()&&a2[j]==(int)s.peek()){s.pop();j++;}}return s.size()==0;}public static void main(String[]args){int []a1={1,2,3,4,5,6,7};int []a2={1,2,3,7,6,5,4};int []a3={1,2,3,7,5,6,4};System.out.println(isPopSeqBySimulate(a1,a2));System.out.println(isPopSeqBySimulate(a1,a3));System.out.println(isPopSeqByNO(a2));System.out.println(isPopSeqByNO(a3));}}