题解 | #火车进站#

使用队列和栈来做遍历，相对来说好理解一些。队列是FIFO，栈是LIFO，队列表示待进站火车，栈表示已进栈火车，然后只需要判断当队列和栈都为空时，即表示出站成功一种方案。

public class Main { 
	public static void main(String[] args) { 
	  Scanner in = new Scanner(System.in);    
	  while (in.hasNext()) {            
	  int n = in.nextInt();           
	  // 待进站火车，用队列存储            
	  Queue<Integer> wctQueue = new LinkedList<>();           
	  for (int i = 0; i < n; i++) {       
		  wctQueue.offer(in.nextInt());           
	  }           
	  // 已进站火车，用栈存储            
	  Stack<Integer> hotStack = new Stack<>();           
	  // 出站火车结果           
	  List<String> outputTrips = new ArrayList<>();            
	  // 开始遍历火车            
	  tripOutIn(wctQueue, hotStack, "", outputTrips);            
	  // 排序           
	  Collections.sort(outputTrips);           
	  outputTrips.forEach(System.out::println);       
	  }    
	}    
  
	private static void tripOutIn(Queue<Integer> wctQueue, Stack<Integer> hotStack, String outputTrip, List<String> outputTrips) {      
	 // 待进站和已出站都为空，则表示已遍历结束，添加结果        
	 if (wctQueue.isEmpty() && hotStack.isEmpty()) {           
	   outputTrips.add(outputTrip);            
	   return;       
	 }     

	 // 开始进站        
	 if (!wctQueue.isEmpty()) {           
	   // 克隆不影响原来的数据            
	   Queue<Integer> tempQueue = new LinkedList<>(wctQueue);            
	   Stack<Integer> tempStack = (Stack<Integer>) hotStack.clone();       
	   tempStack.push(tempQueue.poll());            
	   tripOutIn(tempQueue, tempStack, outputTrip, outputTrips);       
	 }       

	 // 开始出站        
	 if (!hotStack.isEmpty()) {            
	   // 克隆不影响原来的数据            
	   Queue<Integer> tempQueue = new LinkedList<>(wctQueue);            
	   Stack<Integer> tempStack = (Stack<Integer>) hotStack.clone();           
	   String tempOpt = outputTrip + tempStack.pop() + " ";            
	   tripOutIn(tempQueue, tempStack, tempOpt, outputTrips);        
	 }    
   }
}