火车进站-回溯

解题思路
这道题类似于全排列的问题，利用回溯的想法
我们要想求出所有的可能出栈队列
1.只要入站车辆还有，就可以选择是否入栈
2.只要栈非空，就可以选择是否出栈
为了遍历出所有可能的结果，需要回溯
如果此时入栈了，回溯回来记得再出栈（选择-回溯-撤销），出栈也一样
最后一定要有basecase：全部入栈出栈完毕之后，需要将结果存入结果集中（临时结果需要置空）

最后字典序输出：我们以结果的形式转化为字符串，之后排序完再输出

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            //火车数
            int n=input.nextInt();
            //记录入站序列
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=input.nextInt();
            }
            //结果集
            List<List<Integer>> result=new ArrayList<>();
            //回溯完了，result就是结果
            huisu(result,new ArrayList<>(),arr,n,new Stack<Integer>(),0,0);
            //对result进行字典序排序：先转换为字符串数组再排序
            StringBuilder sb=new StringBuilder();
            List<String> result2=new ArrayList<>();
            for(List<Integer> list :result){
                sb=new StringBuilder();
                for(int i=0;i< list.size();i++){
                    sb.append(list.get(i));
                    if( i != list.size()-1){//不是最后一个,加空格
                        sb.append(" ");
                    }
                }
                result2.add(sb.toString());
            }
            Collections.sort(result2);
            for(String s:result2){
                System.out.println(s);
            }
        }
    }
    //result:结果集，temp：临时出车路径，arr:入站序列，n：火车数 stack：火车站 i:出栈序列位置 j：入站序列位置
    public static void huisu(List<List<Integer>> result,List<Integer> temp,int[] arr,int n,Stack<Integer> stack,int i,int j){
        //base case:全部出栈入栈完毕，则存入结果集
        if(i==n && j==n){
            result.add(new ArrayList<Integer>(temp));
            temp=new ArrayList<>();
            return ;
        }
        //选择进站（入栈序列不为空）:入栈序列不为空，就可以选择。选择之后递归，之后再撤销选择
        if(j != n){
            stack.push(arr[j]);
            huisu(result,temp,arr,n,stack,i,j+1);
            stack.pop();
        }
        //栈顶的元素出栈：也是可选的(栈不空就可以操作)
        if( !stack.isEmpty()){
            int x=stack.pop();
            temp.add(x);
            huisu(result,temp,arr,n,stack,i+1,j);
            temp.remove(temp.size()-1);//再去除最后一个
            stack.push(x);//再压进去
        }
    }
}