问题 B: 不同出栈情况(栈和队列)

梦里梦外; 2022-03-22 02:30 274阅读 0赞

### 题目描叙： ###

假设有n个元素依次进栈，给出他们不同的出栈情况。输入n与元素。  
输入  
3  
1 2 3  
输出  
1 2 3  
1 3 2  
3 2 1  
2 1 3  
2 3 1  
样例输入 Copy  
2  
1 2  
样例输出 Copy  
1 2  
2 1  
题目链接：[http://120.78.162.102/problem.php?cid=1440&pid=1][http_120.78.162.102_problem.php_cid_1440_pid_1]  
分析：  
本题第一反应便是无从下手。同时通过不断在纸上模拟，会自然地想到回溯这方面去。但是怎么回，确实一个问题。

n个元素是依次进去栈的。即只有将第i个元素进栈，第i+1个元素才会执行进栈操作。

我们可以想到，在第i个元素进栈后，每一步操作，有且只有两种情况：第一种第i+1个元素进栈。第二种第i个元素出栈（同样在第i个元素出栈后，也有且只有两种可能：第一种第i+1个元素进栈。第二种，第i-1个元素出栈）。

同时，注意，出栈操作执行的前提是栈里面必须有元素（即S.top>=0），否则，只能执行进栈操作。

分析至此，大体思路已明确。不过具体实施，却仍有一定的困难。  
我们需要保存每一次出栈的操作。并且，在没有元素能够进栈的时候（即所有元素都已进过栈），输出之前保存的出栈序列。

故，我们可以利用一个prestack数组来保存每一次出栈的元素。  
具体代码如下：

#include"stdio.h"
    #include"string.h"
    //SqStack这是个栈的结构 
    typedef struct
    {
        int data[100];
        int top;
    }SqStack;
    /*定义一下全局变量，一个栈变量S，一个N（表示有多少个元素）*/
    /*Original数组（保存要处理的N个元素）*/
    /*Prestack数组（保存每一次出栈的元素）*/
    /*count 是我为了统计有多少种进出栈的可能性而定义的*/
    SqStack S;
    int N;
    int Original[100];
    int Prestack[100];
    long long count;
    /*核心代码，此代码中，需要完成当没有元素能够进栈的时候， 我要输出出栈的序列。完成第i个元素进栈的时候，接下来要进行的两种操作。*/
    //i表示有多少个元素已经进栈
    /*j为Prestack数组的下标，表示如果为出栈操作， 则需将出栈元素的值赋给Prestack[j]。*/
    void Put(int i,int j)
    {
        int k;
       //当i==N的时候，就表示没有元素能够进栈了。
       //需执行打印Prestack数组的操作 
        if(i==N)
        {
            count++;
            /*在打印Prestack数组之前， 要先将栈中的元素全部以出栈的序列依次赋值给Prestacj*/
            for(i=S.top;i>=0;i--)
                Prestack[j++]=S.data[i];
            for(i=0;i<N-1;i++)
                printf("%d ",Prestack[i]);
            printf("%d\n",Prestack[i]);
            return ;
        }
        //下面是执行两种可能性（即接下来的操作时进栈元素还是出栈元素）
        //在此程序中，k==1的时候是执行出栈操作。k==2的时候，执行入栈操作
        for(k=1;k<=2;k++)
        {
            switch(k)
            {
                case 1:
                if(S.top>=0)//出栈操作的前提条件
                     {
                         Prestack[j]=S.data[S.top];//将栈顶元素出栈
                         S.top--;                           //表示栈顶的变量值减1
                      /*在执行Put，i不变是因为此操作中没有元素进栈，所以i不变；
                       j+1是因为在此操作中栈顶元素出栈。Prestack[j]得到一个值*/
                         Put(i,j+1);
                     /*下面两个语句是回溯的体现，需要恢复至未执行出栈时的情况；
                     以便不影响当k==2的时候的进栈操作*/
                         S.top++;
                         S.data[S.top]=Prestack[j];
                     }
                break;
                case 2:
               //下面为进栈操作，基本思想如出栈操作
                    S.top++;
                    S.data[S.top]=Original[i];
                    Put(i+1,j);
                    S.top--;
                    break;
            }
        }
    }
    int main()
    {
        int i;
        while(~scanf("%d",&N))
        {
            S.top=-1;count=0;
            for(i=0;i<N;i++)
                scanf("%d",&Original[i]);
            Put(0,0);
            printf("一共有%lld种出栈方式.\n",count);
        }
    }

[http_120.78.162.102_problem.php_cid_1440_pid_1]: http://120.78.162.102/problem.php?cid=1440&pid=1