java自主顺序栈实现 假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列并输出到命令行

思路：

假设当前栈中已经有一些元素，它们的出栈顺序为已知。现在要将剩余的所有元素按照任意顺序压入栈中，然后依次弹出元素，得到一个新的出栈序列。如果这个新的出栈序列和已知的出栈序列相同，则说明这个新的出栈序列是合法的。因此，我们可以采用递归的方式，依次枚举每个元素作为下一个出栈元素的可能性，然后对剩余元素递归调用求解。

具体实现步骤如下：

1. 定义一个数组stack，用来存储当前栈中的元素；
2. 定义一个栈顶指针top，初始值为-1；
3. 定义一个数组output，用来存储当前已知的出栈序列；
4. 如果所有元素都已经出栈，那么输出当前已知的出栈序列，并返回；
5. 否则，依次枚举每个元素作为下一个出栈元素的可能性，对剩余元素递归调用求解；
6. 在递归调用结束后，需要将当前枚举的元素压回栈中，以便继续枚举其他元素。

Java代码实现：

public class Stack {
    private int[] stack; // 栈数组
    private int top; // 栈顶指针

    public Stack(int size) {
        stack = new int[size];
        top = -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == stack.length - 1;
    }

    public void push(int x) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = x;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }

    public static void main(String[] args) {
        int n = 3; // 栈中元素个数
        int[] output = new int[n]; // 已知的出栈序列
        Stack stack = new Stack(n);
        findAllPermutations(stack, output, n, 0);
    }

    private static void findAllPermutations(Stack stack, int[] output, int n, int k) {
        if (k == n) {
            // 所有元素都已经出栈，输出当前已知的出栈序列
            for (int i = 0; i < n; i++) {
                System.out.print(output[i] + " ");
            }
            System.out.println();
            return;
        }
        // 枚举每个元素作为下一个出栈元素的可能性
        for (int i = 1; i <= n; i++) {
            boolean found = false;
            for (int j = 0; j < k; j++) {
                if (output[j] == i) {
                    // 如果当前元素已经在已知的出栈序列中出现过，则不考虑它
                    found = true;
                    break;
                }
            }
            if (!found) {
                // 如果当前元素还没有出现在已知的出栈序列中，则将它压入栈中
                stack.push(i);
                // 对剩余元素递归调用求解
                findAllPermutations(stack, output, n, k + 1);
                // 在递归调用结束后，需要将当前枚举的元素压回栈中
                stack.pop();
            }
        }
    }
}