java堆栈的问题

Question

求高手指教
栈的push、pop序列。具体描述，输入两个整数序列。其中一个序列表示栈的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序列。
代码如何实现？

Answer 1

入栈：1 2 3 4 5
可能出栈：
5 4 3 2 1 
4 5 3 2 1 
4 3 5 2 1 
4 3 2 5 1 
4 3 2 1 5 
3 5 4 2 1 
3 4 5 2 1 
3 4 2 5 1 
3 4 2 1 5 
3 2 5 4 1 
3 2 4 5 1 
3 2 4 1 5 
3 2 1 5 4 
3 2 1 4 5 
2 5 4 3 1 
2 4 5 3 1 
2 4 3 5 1 
2 4 3 1 5 
2 3 5 4 1 
2 3 4 5 1 
2 3 4 1 5 
2 3 1 5 4 
2 3 1 4 5 
2 1 5 4 3 
2 1 4 5 3 
2 1 4 3 5 
2 1 3 5 4 
2 1 3 4 5 
1 5 4 3 2 
1 4 5 3 2 
1 4 3 5 2 
1 4 3 2 5 
1 3 5 4 2 
1 3 4 5 2 
1 3 4 2 5 
1 3 2 5 4 
1 3 2 4 5 
1 2 5 4 3 
1 2 4 5 3 
1 2 4 3 5 
1 2 3 5 4 
1 2 3 4 5 附相关算法:import java.util.LinkedList;
import java.util.Stack;public class TestIO {
  /**
 * 穷举每一种可能的出栈序列
 * @param inQueue
 * @param stack
 * @param outQueue
 */
public static void getStackSequence(LinkedList<String> inQueue,Stack<String> stack,LinkedList<String> outQueue){
 if(inQueue.isEmpty()&&stack.isEmpty()){
   //输出可能的出栈序列
 while(!outQueue.isEmpty()){
 System.out.print(outQueue.poll()+" ");
 }
 System.out.println();
   }else if(!inQueue.isEmpty()&&!stack.isEmpty()){ 
   //保存现场
 LinkedList<String> tempInQueue=new LinkedList<String>(inQueue);
   LinkedList<String> tempOutQueue=new LinkedList<String>(outQueue);
   Stack<String> tempStack=new Stack<String>();
   for(int i=0;i<stack.size();i++) tempStack.push(stack.get(i));
   //队首元素入栈
   stack.push(inQueue.poll());
 getStackSequence(inQueue, stack, outQueue);
 //还原现场
 inQueue=tempInQueue;
 outQueue=tempOutQueue;
 stack=tempStack;
 //栈顶元素出栈
 outQueue.offer(stack.pop());
 getStackSequence(inQueue, stack, outQueue);
 }else if(!inQueue.isEmpty()&&stack.isEmpty()){
 //队首元素入栈
   stack.push(inQueue.poll());
   getStackSequence(inQueue, stack, outQueue);
 }else if(inQueue.isEmpty()&&!stack.isEmpty()){
 //栈顶元素出栈
 outQueue.offer(stack.pop());
 getStackSequence(inQueue, stack, outQueue);
 }else{
 
 }
 }

/**
 * 封装输出，获得内部算法所需要的接口
 * @param in
 * @param out
 */
private static void init(String[] in){
 Stack<String> stack=new Stack<String>();
 LinkedList<String> outQueue=new LinkedList<String>();
 LinkedList<String> inQueue=new LinkedList<String>();
 for(int i=0;i<in.length;i++) inQueue.add(in[i]);
   getStackSequence(inQueue, stack, outQueue);
   }

 public static void main(String[] args){
 String[] in={"1","2","3","4","5"}; //入栈顺序
   init(in);
   }
}