火车进站

定义全局栈保存在车站里的火车，用resList收集每一种结果。记录出站和入站的火车数量，若出站和入站数量都等于火车数量时，说明遍历完成，保存结果到resList。
当入站火车数量< 火车总数时，不断进站，递归进站火车+1，然后回溯不进站（出站），当站里（栈）的火车不为空时，将火车出站，递归出站火车+1并保存当前结果。
回溯（不出站）。如此遍历结束时，resList收集满了所有结果。此时对结果进行字典序排序后依次输出控制台即可。
import java.util.*;
public class Main {
    static Stack<Integer> st = new Stack<>();
    static List<String> resList = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++){
                nums[i] = in.nextInt();
            }
            backtracking(nums, 0, 0, "");
            Collections.sort(resList);
            for (String res : resList){
                System.out.println(res);
            }
        }
    }
    private static void backtracking(int[] nums, int popNum, int pushedNum, String res){
        if (popNum == nums.length){
            resList.add(res);
            return;
        }
        if (pushedNum < nums.length){
            st.push(nums[pushedNum]);
            backtracking(nums, popNum, pushedNum + 1, res);
            st.pop();
        }
        if (!st.isEmpty()){
            int train = st.pop();
            backtracking(nums, popNum + 1, pushedNum, res + train + " ");
            st.push(train);
        }

    }
} 

参照牛客931628554号的代码，对变量名做了一些优化，添加一些注释

import java.util.Scanner;
import java.util.*;


public class Main {
    static List<String> res = new ArrayList<>();   //存放结果，也就是所有可能的出站序列
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            res.clear();
            int n = in.nextInt();//火车的数量
            int[] trains = new int[n];//存放火车编号
            Stack<Integer> station = new Stack<>();//用栈表示车站，只能先进后出
            for (int i = 0; i < n; i++) {
                trains[i] = in.nextInt();
            }
            trainOut(trains, 0, station, "", 0);
            Collections.sort(res); 
            for (String s : res) {
                System.out.println(s);
            }
        }
        in.close();
    }
    public static void trainOut(int[] trains, int in, Stack<Integer> station,
                                String res_temp, int out) {
        if (out == trains.length) {   //out表示已经出站的火车数量。当所有火车出站时，表示一个出站序列完成，将其添加到结果中
            res.add(res_temp);
        }
        if (!station.empty()) {  //当车站还有火车时
            int train = station.pop();  //出站一辆火车
            trainOut(trains, in, station, res_temp + train + " ", out + 1);//该出站火车添加到当前出站序列红，出站火车数量+1
            station.push(train);
        }
        if (in < trains.length) { //当还有火车未进站时
            station.push(trains[in]);//进站一辆火车
            trainOut(trains, in + 1, station, res_temp, out);//已进站火车数量+1
            station.pop();
        }
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 获取输入火车数
        int n = in.nextInt();
        // 定义一个队列，表示需要进入的火车
        Queue<String> que = new LinkedList<>();
        // 定义一个栈，模拟火车进出站
        Stack<String> stack = new Stack<>();
        // 定义一个List集合，用于存放火车出栈顺序集合
        List<String> list = new ArrayList<>();
        // 定义一个String，表示出栈顺序
        String pop = "";
        // 将火车进入队列
        for (int i = 0; i < n; i++) {
            que.offer(String.valueOf(in.nextInt()));
        }
        // 模拟火车进出站
        trainEnter(que, stack, list, pop);
        // 对出栈顺序集合进行排序
        Collections.sort(list);
        // 输出结果
        list.forEach(p-> {
            System.out.println(p);
        });
    }

    /**
     * 模拟火车进站或出栈.
     */
    private static void trainEnter(Queue<String> que, Stack<String> stack,
                                   List<String> list, String pop) {
        if (que.isEmpty() && stack.isEmpty()) {
            // 进站队列和栈都为null，则return,将出栈顺序添加到list
            list.add(pop);
            return;
        }
        // 主要车站还存在车，遍出栈
        if (!stack.isEmpty()) {
            // 先克隆,保证数据的原始性质
            Queue<String> tempQueue = new LinkedList<>(que);
            Stack<String> tempStack = (Stack<String>) stack.clone();
            // 栈顶出栈
            String tempOutQueue = pop + (tempStack.pop() + " ");
            // 递归调用，下一个车辆进站
            trainEnter(tempQueue, tempStack, list, tempOutQueue);
        }
        // 主要车队不为空，遍进站
        if (!que.isEmpty()) {
            // 先克隆,保证数据的原始性质
            Queue<String> tempQueue = new LinkedList<>(que);
            Stack<String> tempStack = (Stack<String>) stack.clone();
            // 后车出队列，返回队列第一个元素，并删除
            String train = tempQueue.poll();
            // 后车进站
            tempStack.push(train);
            // 递归调用，下一个车辆进站
            trainEnter(tempQueue, tempStack, list, pop);
        }
    }
}

import java.util.*;

public class Main {

    private static boolean[] used = null;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        used = new boolean[n + 1];

        int[] nums = new int[n];
        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        dfs(n, nums, tmp, 0);

        sc.close();
    }

    private static void dfs(int n, int[] nums, int[] tmp, int step) {
        if (step == nums.length) {
            if (isValid(nums, tmp)) {
                System.out.println(printResult(tmp));
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }

            used[i] = true;
            tmp[step] = i;
            dfs(n, nums, tmp, step + 1);
            used[i] = false;
        }
    }

    private static boolean isValid(int[] nums, int[] tmp) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        Set<Integer> set = new HashSet<>();
        int idx = 0;
        for (int i = 0; i < tmp.length; i++) {
            while (!set.contains(tmp[i])) {
                set.add(nums[idx]);
                idx++;
            }

            for (int j = map.get(tmp[i]) + 1; j < idx; j++) {
                if (set.contains(nums[j])) {
                    return false;
                }
            }
            set.remove(tmp[i]);
        }
        return true;
    }

    private static String printResult(int[] tmp) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tmp.length - 1; i++) {
            sb.append(tmp[i]).append(" ");
        }
        sb.append(tmp[tmp.length - 1]);
        return sb.toString();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int cnt = in.nextInt();
            int[] arr = new int[cnt];
            for (int i = 0; i < cnt; i++) {
                arr[i] = in.nextInt();
            }
            pp(arr);
        }
    }
    
    private static void pp(int[] arr) {
        List<Integer> output = new ArrayList<>();
        List<Integer> op = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        l = new ArrayList<>();
        dfs(arr, 0, output, stack);
        l.sort(String::compareTo);
        for (String s : l) {
            System.out.println(s);
        }
    }
    
    private static List<String> l = new ArrayList<>();
    
    private static void dfs(int[] arr, int idx, List<Integer> output, Stack<Integer> stack) {
        if (idx == arr.length) {
            print(output, stack);
            return;
        }
        // buffer -> out
        if (!stack.isEmpty()) {
            Integer t = stack.pop();
            output.add(t);
            dfs(arr,idx,output,stack);
            output.remove(t);
            stack.push(t);
        }
        // buffer
        stack.push(arr[idx]);
        dfs(arr, idx + 1, output, stack);
        stack.pop();
    }
    
    private static void print(List<Integer> list, Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder(32);
        for (Integer i : list) {
            sb.append(i).append(' ');
        }
        for (int i = stack.size() -1; i >= 0; i--) {
            sb.append(stack.get(i)).append(' ');
        }
        //System.out.println(sb.toString());
        l.add(sb.toString());
    }
}

通过模拟栈的操作来生成所有可能的序列，超级好理解：

import java.util.*;

public class Main {
    // 生成数字的入栈出栈操作序列，使用回溯进行生成
    public void generateStackOperator(int[] nums, int n, int p, int q,
                                      List<List<Integer>> ret, List<Integer> sub) {
        if (q == n) {
            ret.add(new ArrayList<>(sub));
            return;
        }
        if (p < n) {
            sub.add(1);
            p++;
            generateStackOperator(nums, n, p, q, ret, sub);
            sub.remove(sub.size() - 1);
            p--;
        }
        if (p > q) {
            sub.add(0);
            q++;
            generateStackOperator(nums, n, p, q, ret, sub);
            sub.remove(sub.size() - 1);
            q--;
        }
    }

    // 模拟栈的入栈出栈顺序，将出栈结果放入结果集中
    public List<List<Integer>> processStackSeries(int[] nums, List<List<Integer>> operatorSeries) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        Deque<Integer> stack = new LinkedList<Integer>();

        for (List<Integer> series : operatorSeries) {
            int start = 0;
            List<Integer> subRet = new ArrayList<>();
            for (Integer op : series) {
                if (op == 1) {
                    stack.push(nums[start]);
                    start++;
                } else {
                    // op is 0
                    subRet.add(stack.pop());
                }
            }
            ret.add(subRet);
        }

        return ret;
    }

    // 利用一个栈，通过模拟栈的入栈和出栈操作，来获得所有可能的序列
    public static void main(String[] args) {
        Main obj = new Main();

        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            int trainCounts = sc.nextInt();
            int[] trains = new int[trainCounts];
            for (int i = 0; i < trainCounts; i++) {
                trains[i] = sc.nextInt();
            }

            List<List<Integer>> operatorSeries = new ArrayList<List<Integer>>();
            List<Integer> subSeries = new ArrayList<>();
            obj.generateStackOperator(trains, trains.length, 0, 0, operatorSeries, subSeries);

            List<List<Integer>> ret = obj.processStackSeries(trains, operatorSeries);
            Collections.sort(ret, new Comparator<List<Integer>>() {
                @Override
                public int compare(List<Integer> o1, List<Integer> o2) {
                    int length = o1.size();
                    int res = 0;
                    for (int i = 0; i < length; i++) {
                        if (o1.get(i) < o2.get(i)) {
                            res = -1;
                            break;
                        } else if (o1.get(i) == o2.get(i)) {
                            if (i == length - 1) {
                                return 0;
                            } else {
                                continue;
                            }
                        } else {
                            res = 1;
                            break;
                        }
                    }
                    return res;
                }
            });

            for (List<Integer> subRet : ret) {
                for (Integer n : subRet) {
                    System.out.print(n);
                    System.out.print(" ");
                }
                System.out.println();
            }

        }
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            String[] orders = new String[n];
            for (int i = 0; i < n; i++) {
                orders[i] = sc.next();
            }
            Stack<String> stack = new Stack<>();
            List<String> resList = new ArrayList<>();
            dfs(0, orders, new ArrayList<>(), resList, stack);
            resList.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    char[] chars1=o1.toCharArray();
                    char[] chars2=o2.toCharArray();
                    int i=0;
                    while(i<chars1.length && i<chars2.length){
                        if(chars1[i]>chars2[i]){
                            return 1;
                        }else if(chars1[i]<chars2[i]){
                            return -1;
                        }else{
                            i++;
                        }
                    }
                    if(i==chars1.length){  //o1到头
                        return -1;
                    }
                    if(i== chars2.length){ //o2到头
                        return 1;
                    }
                    return 0;
                }
            });
            for (String s :
                    resList) {
                System.out.println(s);
            }
        }
    }

    public static void dfs(int index, String[] ops, List<String> record,
                           List<String> res, Stack<String> stack) {
        if (index == ops.length) {
            List<String> temp = new ArrayList<>(record);
            Stack<String> tStack = new Stack<>();
            tStack.addAll(stack);
            while(!tStack.empty()) {
                temp.add(tStack.pop());
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < temp.size() - 1; i++) {
                sb.append(temp.get(i)).append(" ");
            }
            sb.append(temp.get(temp.size() - 1));
            res.add(sb.toString());
        } else {
            if(!stack.isEmpty()) {
                String temp = stack.pop();
                record.add(temp);
                dfs(index, ops, record, res, stack);
                record.remove(record.size() - 1);
                stack.add(temp);
            }
            stack.add(ops[index]);
            dfs(index + 1, ops, record, res, stack);
            stack.pop();
        }

    }
}

import java.util.*;
public class Main {
    //存放结果
    public static List<String> list;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            //初始化结果集
            list = new ArrayList<>();
            int n = sc.nextInt();
            //保存站外火车
            int[] arr= new int[n];
            //保存站内火车
            LinkedList<Integer> stack = new LinkedList<>();
            for(int i = 0;i < n;i++){
                arr[i] = sc.nextInt();
            }
            //执行方法
            trainOut(arr,stack,"",0,0);
            Collections.sort(list);
            list.forEach(s->System.out.println(s));
        }
    }
    public static void trainOut(int[] arr,LinkedList<Integer> stack,String result,int in,int out){
        if(out == arr.length){
            list.add(result);
        }
        if(!stack.isEmpty()){
            int tmp = stack.pop();
            trainOut(arr,stack,result + tmp + " ",in,out+1);
            stack.push(tmp);
        }
        if(in < arr.length){
            stack.push(arr[in]);
            trainOut(arr,stack,result,in+1,out);
            stack.pop();
        }
    }
}

import java.util.*;

public class Main{

    static List<String> l = new ArrayList<>(); //储存结果

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            l.clear(); //静态变量，每次先清空
            int nums = in.nextInt();
            int[] id = new int[nums];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < nums; i++) {
                id[i] = in.nextInt();
            }
            trainOut(id, 0, stack, "", 0);
           //对结果集排序
            Collections.sort(l); 
            for (String str : l) {
                System.out.println(str);
            }
        }
        in.close();
    }

//i为入栈次数，n为出栈次数，str存储一趟结果

    public static void trainOut(int[] id, int i, Stack<Integer> s, String str, int n) {
        if (n == id.length) {
            l.add(str); //如果所有火车均出栈则将当前结果保存
        }

        if (!s.empty()) { //栈非空时出栈
            int temp = s.pop();
            trainOut(id, i, s, str + temp + " ", n + 1);
            s.push(temp); //恢复现场
        }

        if (i < id.length) {
            s.push(id[i]);
            trainOut(id, i + 1, s, str, n);
            s.pop(); //恢复现场

        }
    }
}