请写一个输入ABCD四个字母入栈,输出全部可能出栈顺序的代码
时间: 2024-03-01 07:55:54 浏览: 245
以下是用Java实现输入ABCD四个字母入栈,输出全部可能出栈顺序的代码:
```java
import java.util.ArrayList;
import java.util.Stack;
public class StackPermutation {
public static void main(String[] args) {
char[] input = {'A', 'B', 'C', 'D'};
ArrayList<String> result = new ArrayList<String>();
Stack<Character> stack = new Stack<Character>();
permutation(input, 0, stack, result);
for (String s : result) {
System.out.println(s);
}
}
public static void permutation(char[] input, int index, Stack<Character> stack, ArrayList<String> result) {
if (index == input.length && stack.isEmpty()) {
StringBuilder sb = new StringBuilder();
for (char c : input) {
sb.append(c);
}
result.add(sb.toString());
} else {
if (index < input.length) {
stack.push(input[index]);
permutation(input, index + 1, stack, result);
stack.pop();
}
if (!stack.isEmpty()) {
char c = stack.pop();
input[index] = c;
permutation(input, index, stack, result);
stack.push(c);
input[index] = 0;
}
}
}
}
```
该程序使用递归实现了求出所有输入ABCD四个字母入栈后的所有可能出栈顺序。其中,permutation()方法用于递归计算不同的出栈顺序,index参数表示当前处理的字母在输入序列中的下标位置,stack参数表示当前栈的状态,result参数表示所有不同出栈顺序的列表。在每次递归中,程序分别考虑将当前字母入栈和出栈的两种情况,直到处理完所有字母并且栈为空。最后,程序将所有不同出栈顺序保存到一个ArrayList中并输出。
阅读全文