输出所有可能的出栈顺序

abc的所有可能的出栈顺序 

递归三部曲:

1.确定返回值和参数的类型:

无返回值

要入栈元素的下标n

栈 Stack<Character>

字符串out记录出栈路径

要入栈的字符串 String temp

2.确定递归结束条件

当n==temp.length时表示字符串都入栈了

当栈为空时表示之前入栈的字符都出栈了

递归结束条件:

n == temp.length() && stk.isEmpty()
3.确定单层逻辑

入栈,将下标为n的元素入栈,入栈元素下标n加1

 fun(n + 1, stk, out, temp);

出栈,出栈路径out拼接上栈顶元素,栈顶元素出栈,入栈元素下标不变

 fun(n, stk, temp1, temp);

   if (n < temp.length()) {//入栈stk.push(temp.charAt(n));fun(n + 1, stk, out, temp);stk.pop();}if (!stk.isEmpty()) {//出栈Character peek = stk.peek();String temp1 = out + stk.pop();fun(n, stk, temp1, temp);stk.push(peek);}

总体代码: 

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String temp = in.next();fun(0, new Stack<Character>(), "", temp);}static void fun(int n, Stack<Character> stk, String out, String temp) {if (n == temp.length() && stk.isEmpty()) {System.out.println(out);return;} else {if (n < temp.length()) {//入栈stk.push(temp.charAt(n));fun(n + 1, stk, out, temp);stk.pop();}if (!stk.isEmpty()) {//出栈Character peek = stk.peek();String temp1 = out + stk.pop();fun(n, stk, temp1, temp);stk.push(peek);}}}}