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.hasNextInt()) { // 注意 while 处理多个 case int a = in.nextInt(); int[] waStack = new int[a]; for (int i = 0; i < a; i++) { waStack[i] = in.nextInt(); } LinkedList<Integer> stackInsert = new LinkedList<>(); for (int i = 0; i < waStack.length; i++) { stackInsert.add(waStack[i]); } visitStack(stackInsert, new Stack<Integer>(), new LinkedList<Integer>(), waStack.length); Collections.sort(allPopStack); for (String s : allPopStack) { System.out.println(s); } } } public static void visitStack(LinkedList<Integer> insert, Stack<Integer> stack, LinkedList<Integer> record, int size) { //栈已经全部入完 if (record.size() == size) { //已经全部记录 StringBuilder builder = new StringBuilder(); for (Integer integer : record) { builder.append(integer).append(" "); } allPopStack.add(builder.toString().trim()); return; } //入栈, 还有数据可以入栈的时候,才能 if (insert.size() > 0) { Integer inte = insert.pollFirst(); stack.push(inte); visitStack(insert, stack, record, size); // 恢复原貌 insert.addFirst(inte); //还回去 stack.pop(); } //出栈 if (stack.size() > 0) { Integer pop = stack.pop(); record.add(pop); visitStack(insert, stack, record, size); stack.push(pop); record.removeLast(); } } }
这个难点是如何 定义三个状态 栈已经全部入完\入栈, 还有数据可以入栈的时候\出栈 并且入栈与出栈的时候需要还原入栈与出栈时候的场景