请教：栈的输出序列问题

renbagshoes

问题如下：

/* 假设有编号1、2、3的三辆列车，顺序进入一个栈式结构的站台，*/

/* 具体输出这3辆车开出站台的所有可能顺序 */


[php]
思路一：
/*如果用栈的后进先出的性质这个思路来解的话，那么有输入序 */

/*列是i,j,k时，并有i<j<k,那么输出序列pi,pj,pk不可能是pj<pk<pi*/

/*如果是这种思路，源程序如下*/

#include <stdio.h>

void changelist(int a[],int t){
        int i,temp;
        if(t==2){
                if(!(a[1]<a[2]&&a[2]<a[0])){
                        for(i=0;i<3;i++)printf("%d",a);
                }
                printf("\t");
        }
        else
                for(i=t;i<3;i++){
                        temp=a[t];a[t]=a;a=temp;

                        changelist(a,t+1);

                        temp=a[t];a[t]=a;a=temp;
                }
}

int main(void){
        int a[3]={1,2,3};
        printf("\n");
        changelist(a,0);
        return 0;
}
[/php]
上面这个方法有个缺憾就是在车增多时，计算量会很大。

[php]思路二：直接生成法(或称模拟法，递归的内容)？？？这个也是我想请教大家的？[/php]

kj501

栈的特点就是后进先出。进去是1,2,3，出来就是3,2,1 。就是这么简单。

renbagshoes

版主，是所有可能顺序，并用除第一种思路外的方法实现

能写出完整的程序最好，先谢过了！

renbagshoes

直接生成法(或称模拟法)。设a1，…，ai是已出栈的编号b1，…，bj是已进栈的编号。而c1，…，ck则是尚未入栈的编号。现在有两种可能，一是将c1进栈，另一个则是将b1出栈，因此，可采用状态递归的办法，从初始状态出发，逐步递归，当全部编号出栈时，所得的就是一种可能的输出序列，由此得出所有的可能输出序列。以下给出算法的描述

当取n=4时，可能的输出顺序有14种，分别是：4321，3421，3241，2431，2341，2314，2143，2134，1234，1432，1324，l342，1243。

kj501

想了半天才明白你的意思。原来题意不是要求一次出栈，而是随机出栈。也就是说，进栈时可能是1, 2, 3, 4，但可能进到12时就先出栈2，再进3，4，最后的出栈顺序为2,4,3,1。这是个排列组合的问题，我想想先。

home_king

修正一下，楼主的n=4的"可能输出序列"存在缺漏，比如说3214就是一种可能。

其实，严格而言，顺序进入栈的输入序列，其输出序列存在以下规律：
序列中任意一个元素x
1.其后面的元素或者都大于x
2.或者小于x的都逆序排列

这样可以得出一个粗略但高效的算法：
n个元素，先输出的元素有n个可能，假设输出为x，其后比x小的元素逆序排列，比x大的元素进行插入，就此涉及排列组合问题，但无需递归结构。

解答并不难，我当时上数据结构课时也设计过这类程序。