设置自己的网站如何被百度收录

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

思路：先将入栈序列放入队列queue中。为入栈序列维护栈结构stack。对出栈序列进行如下操作：

如果栈顶是出栈元素，出栈。
如果栈顶不是出栈元素，在队列中查找出栈元素，并将出栈元素之前的元素出队列，并且压入stack中，如果在队列中没找到对应元素，则为非法序列。

代码如下：

    //例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。//借助一个队列和一个栈结构public boolean IsPopOrder(int [] pushA,int [] popA) {Stack<Integer> seq = new Stack<Integer>();Queue<Integer> queue = new LinkedList<Integer>();if(pushA.length==0 || popA.length==0){return false;}for(int i=0;i<pushA.length;i++){queue.add(pushA[i]);}for(int i=0;i<popA.length;i++){int ele = popA[i];if(!seq.isEmpty() && seq.peek()==ele){  //栈顶元素等于出栈元素，出栈seq.pop();}else{               //栈顶元素不是出栈元素，在队列中查找元素，并将这个元素之前的元素进栈，如果没找到对应的元素，则为非法序列while(!queue.isEmpty() && queue.peek()!=ele){seq.add(queue.poll());}if(queue.isEmpty()){        //队列已经空了，还没找到对应的元素，非法序列return false;}queue.poll();       //将ele元素出队列，因为要从栈中弹出，就不入栈了}}return true;}