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);
      }
}