出栈序列


题目


给定栈的输入序列为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递归。

​ (c) Pop:如果不空,进行pop ,将pop的数存入数组,继续对当前数据Proccess递归。
​ [此步骤要拿一个动态局部变量tmp保留pop出的值]

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

回溯处理(TraceBack)

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

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

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

​ (c) Pop:将数组中元素重新赋值为0,并push回刚刚pop的保留值tmp。

直到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 结束]
}

至此,整个题目完成

拓展:为了解决入栈序列为{ 3, 7, 9, 2, 4 }之类不规律的问题,只需稍加修改。
将 1–n 变为 TitleArray[0] – TitleArray[n - 1]即可实现,核心算法不变。

结语


整个思考过程,给我感触颇深。为了将所有情况列出,更是不容在逻辑上存在一点漏洞。
一次次的疏漏,带来一次次的苦恼。
当正确的结果出现时,无限的激动与欣喜,或许这也就是思考的魅力吧。

这算是我(偶然)做的第二道算法题了,希望未来的自己看到这篇文章时,会对稚嫩的我,露出欣慰的笑容。


  目录