题解 | #出栈顺序#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {

static List<String> allPopStack = new ArrayList<>();

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // 注意 hasNext 和 hasNextLine 的区别
    while (in.hasNextLine()) { // 注意 while 处理多个 case
        String a = in.nextLine();
        char[] waStack = a.toCharArray();
        LinkedList<Character> characters = new LinkedList<>();
        for (int i = 0; i < waStack.length; i++) {
            characters.add(waStack[i]);
        }
        visitStack(characters, new Stack<Character>(), new LinkedList<Character>(),
                   waStack.length);
        Collections.sort(allPopStack);
        for (String s : allPopStack) {
            System.out.println(s);
        }
    }

}

public static void visitStack(LinkedList<Character> insert,
                              Stack<Character> stack, LinkedList<Character> record, int size) {
    //栈已经全部入完
    if (record.size() == size) {
        //已经全部记录
        StringBuilder builder = new StringBuilder();
        for (Character character : record) {
            builder.append(character);
        }
        allPopStack.add(builder.toString());
        return;
    }

    //入栈, 还有数据可以入栈的时候,才能
    if (insert.size() > 0) {
        Character character = insert.pollFirst();
        stack.push(character);
        visitStack(insert, stack, record, size);

        // 恢复原貌
        insert.addFirst(character);
        //还回去
        stack.pop();
    }

    //出栈
    if (stack.size() > 0) {
        Character pop = stack.pop();
        record.add(pop);
        visitStack(insert, stack, record, size);

        stack.push(pop);
        record.removeLast();
    }
}

}