题目

给定栈的输入序列为1、2、3、…、n，设计算法求出所有可能的出栈序列，并统计个数。

示例：
输入： 4
输出：
NO.1 is: 4321
NO.2 is: 3421
NO.3 is: 3241
NO.4 is: 3214
NO.5 is: 2431
NO.6 is: 2341
NO.7 is: 2314
NO.8 is: 2143
NO.9 is: 2134
NO.10 is: 1432
NO.11 is: 1342
NO.12 is: 1324
NO.13 is: 1243
NO.14 is: 1234

思路解析

1. 引例

让我们先来举个例子——对于{ 1, 2, 3 } 的入栈序列来说，1，2，3均为待入栈的数据。
首先，对 1 进行处理，因为栈中还没有数据，不能出栈，只能入栈。

栈中序列：{ 1 } 已出栈序列：暂无

接着，对2进行处理，因为栈中有1，所以既可以push入2，也可以pop出1。
a) 若push：

栈中序列：{ 2, 1 } 已出栈序列：暂无

push后，向后处理最后一个 3 即可

b) 若pop：

栈中序列：暂无已出栈序列 : { 1 }

pop后继续对尚未入栈的2进行处理

……
如此循环直到所有元素都入过栈，即1，2，3均被处理完成。
此时，已出栈序列加上栈中尚未出栈序列即为一种答案。
【因为最后栈中剩余的是一起pop出栈】

2. 完整思路

【递归 + 回溯】
使用栈S模拟入栈和出栈的过程，同时使用数组array进行已出栈元素的记录

使用数组是为了方便输出；
创建数组时，分配n个int内存，初始化全为0；
【0表示此处尚无出栈元素，同时也可作为输出终止的标志】

递归处理（Recursion Proccess）

(a) 判断递归是否结束，若结束，输出出栈序列和栈中尚未出栈序列。
否则的话进行 b 和 c操作。

(b) Push：push后，对下一个数据进行Proccess递归。

对于一条完整的分支，1 – n每个元素都要进行一次push操作和零次或多次pop操作。

回溯处理（TraceBack）

每次递归操作后，进行回溯（将数组array和栈S回到没处理过的状态）。

(a) 仅执行输出，没有改变数据，无需回溯

(b) Push：pop完成回溯即可。

直到1–n都入栈，[ 递归 ]完成，一条分支结束。
直到1–n的 [ 递归+回溯 ] 完成，所有分支结束。
因为整个过程都是向前推进的，回溯只恢复数据，而不恢复进度，所有分支都不重复。

完整代码实现

因为本题在数据结构课程中完成，使用的是自己定义的栈

1. 栈类的创建

template<class ElementType>
class seqStack
{
private:
    ElementType* Data;
    int top;
public:
    seqStack();    // 构造函数
    seqStack(const seqStack<ElementType>& S);  // 拷贝构造函数
    bool Push(ElementType);    // 入栈
    ElementType Pop();    // 出栈
    int GetTop();    // 得到栈顶的值
    ElementType GetTopNum();    // 得到栈顶的元素的值
};

void Print(seqStack<int> s);  //输出栈的序列

2. 核心【递归 + 回溯】

void Proccess(const int n, int* array, int num)
{
    static int number = 0;    // 记录结果的个数
    static seqStack<int> S;    // 栈的创建
    int tmp;    // 用于pop后的回溯
    /* 结束递归 */
    if (num == n + 1)    // 所有元素都已完成入栈操作[即n处理完成]
    {
        number++;    // 结果个数+1
        cout << "NO." << number << " is: ";
        for (int i = 0; array[i] != 0; i++)    // 0 即空
            cout << array[i];
        Print(S);
        cout << endl;
        /* 一条分支结束 */
    }
    /* 未达成结束条件，进行 待入栈数据的push 和 已入栈数据的pop */
    else
    {
        /* 1.Push */
        S.Push(num);
        Proccess(n, array, num + 1);    // 对下一个数据进行递归处理
        S.Pop();    // 回溯
        /* 2.Pop */
        if (S.GetTop() + 1)    // pop的前提是栈不空
        {
            tmp = S.Pop();
            array[num - S.GetTop() - 3] = tmp;    // 记录已出栈元素
            Proccess(n, array, num);    // 继续对该数据进行递归处理【尚未入栈】
            array[num - S.GetTop() - 3] = 0;    // 数组的回溯
            S.Push(tmp);    // 栈的回溯
        }
    }
}

3. 回归题目

int main(void)
{
    int n;
    cout << "Please input the value of n: ";
    cin >> n;
    int* array = new int[n];    // 创建数组
    for (int i = 0; i < n; i++)    // 初始化数组
        array[i] = 0;
    Proccess(n, array, 1);    // 从 1 开始递归 [n 结束]
}