java 顺序栈实现假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。

思路：

我们可以定义两个指针，p1和p2，p1指向输入序列的第一个元素，p2指向输出序列的第一个位置，然后依次将输入序列中的元素压入栈中，每次压入一个元素后，我们检查该元素是否与输出序列的第一个元素相同，如果相同，则将该元素弹出栈，并将输出指针p2向后移动一个位置，直到不能继续弹出为止。这个过程中，我们需要保持栈中元素的顺序与输入序列相同。

当所有元素都被压入栈中后，我们需要检查栈中是否还有元素，如果有，则将其依次弹出，并将其与输出序列中剩余的元素进行比较，如果相同，则将其弹出，并将输出指针p2向后移动一个位置，直到栈中没有元素为止。这个过程中，我们同样需要保持栈中元素的顺序与输入序列相同。

在每一次弹出栈中元素的过程中，我们需要记录下栈中元素的排列方式，当栈中没有元素时，我们就得到了一个可能的输出序列。

代码实现：

import java.util.Stack;

public class StackPermutations {

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4, 5};
        printAllPermutations(input);
    }

    private static void printAllPermutations(int[] input) {
        int n = input.length;
        int[] output = new int[n];
        Stack<Integer> stack = new Stack<Integer>();
        int p1 = 0, p2 = 0, i = 0;
        stack.push(input[p1++]);
        while (p1 <= n && p2 < n) {
            while (stack.peek() != output[p2] && p1 <= n) {
                stack.push(input[p1++]);
            }
            if (stack.peek() == output[p2]) {
                stack.pop();
                p2++;
            } else {
                break;
            }
        }
        if (p1 > n && p2 == n) {
            print(output);
        }
        while (!stack.isEmpty()) {
            output[i++] = stack.pop();
        }
        while (i < n) {
            output[i++] = -1;
        }
        while (true) {
            int j = n - 2;
            while (j >= 0 && output[j] > output[j + 1]) {
                j--;
            }
            if (j < 0) {
                break;
            }
            int k = n - 1;
            while (k > j && output[k] < output[j]) {
                k--;
            }
            swap(output, j, k);
            reverse(output, j + 1, n - 1);
            print(output);
        }
    }

    private static void swap(int[] output, int i, int j) {
        int temp = output[i];
        output[i] = output[j];
        output[j] = temp;
    }

    private static void reverse(int[] output, int i, int j) {
        while (i < j) {
            swap(output, i++, j--);
        }
    }

    private static void print(int[] output) {
        for (int i : output) {
            System.out.print(i);
        }
        System.out.println();
    }
}

时间复杂度：$O(n^2)$，因为我们需要生成所有可能的输出序列。