1，2，3，4依次进栈，出栈随时，写一算法求出所有可能出栈序列

Question

要求带注释，最好使用C或C++
感谢一楼的回答，但是算法明显不正确，4元素应该有14出栈序列
你的算法只显示8种，少了2143,2134,3214,3241

Answer 1

代码如下：

#define N 4

int m=0,a=0,b=N;/*m表示种数，a表示栈中元素个数，b表示外面还有需要进栈的个数*/

main()

{

inS(a,b);/*首先入栈*/

printf("%d",m);

getch();

}

int inS(int a,int b)/*入栈*/

{

a++;b--;/*入栈栈中元素+1，栈外元素-1 */

if(b>0)/*若栈外有元素，可以入栈*/

inS(a,b);

if(a>0)/*若栈中有元素，可以出栈*/

outS(a,b);

}

int outS(int a,int b)/*出栈*/

{

a--;/*出栈栈中元素-1*/

if(a==0&&b==0)/*若栈中元素和栈外元素都为0个*/

{

m++;/*则此种情况的序列满足条件，种数+1*/

return;

}

if(b>0)

inS(a,b);

if(a>0)

outS(a,b);

}

扩展资料

栈的相关知识点：

顺序栈内容包含数据和栈顶指针(int)，因此采用结构体。

注意：

1、初始时，top指向-1；

2、入栈时，先判断顺序栈是否已满（判断条件：top=maxsize-1）;如果没满，则top++，并将元素值赋给s.top;

3、出栈时，先判断顺序栈是否已空（判断条件：top=-1）;如果没空，则先返回栈顶元素，再top- -。

共享栈

两个顺序栈共享一个一维数组空间，而栈底位置相对不变，两个栈底分别设为一维数组的两端。

note:

(1)栈空：top1==-1&&top2==maxsize;

(2)栈满：top2-top1= 1(此时两个栈顶指针相邻)；

(3)入栈：S.data[++top1]=x或S.data[–top2]=x;

(4)出栈：x=S.data[top1–]或x=S.data[top2++];

(5)共享栈可以更好的利用存储空间，整个存储空间被占满时发生上溢。

参考资料来源：

百度百科——栈

Answer 2

你要算法，从程序中归纳就行了
我想到一种方法，可是有点复杂，要用到树的结构，先给你看个程序，是计算n个元素进栈，可能的出栈系列种数
/*递归求n个元素进栈，可能的出栈系列种数*/
#define N 4
int m=0,a=0,b=N;/*m表示种数，a表示栈中元素个数，b表示外面还有需要进栈的个数*/
main()
{
inS(a,b);/*首先入栈*/
printf("%d",m);
getch();
}

int inS(int a,int b)/*入栈*/
{
a++;b--;/*入栈栈中元素+1，栈外元素-1 */
if(b>0)/*若栈外有元素，可以入栈*/
inS(a,b);
if(a>0)/*若栈中有元素，可以出栈*/
outS(a,b);
}
int outS(int a,int b)/*出栈*/
{
a--;/*出栈栈中元素-1*/
if(a==0&&b==0)/*若栈中元素和栈外元素都为0个*/
{
m++;/*则此种情况的序列满足条件，种数+1*/
return;
}
if(b>0)
inS(a,b);
if(a>0)
outS(a,b);
}
若想输出这些序列，可以建立一个二叉树，二叉树的节点为操作（进栈或出栈），从根节点（第一个入栈）到叶子节点（最后一个出栈）的路径就是每个序列的操作序列，每条路径共有2N个节点，分别为每个元素的入栈和出栈操作，然后通过遍历，将这些节点输出即可
建立这棵树可以用上面的递归建立，也可以用下面的方法建立
①建立一颗深度为2N的满二叉树(根节点深度为1)，其中根节点为IN（入栈），其他左子树为IN，右子树为OUT（出栈），这棵树共有2^(2N-1)个叶子节点，用根节点到叶子节点共有2^(2N-1)条路径
②保留满足下面条件的路径，其他的剔除
1)路径从根到叶出现IN和OUT总次数均为N个
2)路径从根到叶出现 IN次数≥OUT次数(即出栈次数不可能多余入栈次数)

然后输出保留的每条路径上节点类型为OUT的数据，即是出栈序列

剔除方法可由下面方法实现
1根节点赋值为1，
2节点为IN，则此节点赋值为父节点的值+1，节点为OUT，则此节点赋值为父节点的值-1，
3剔除节点的值为负数，或值>N的节点，或叶子节点上的值不=0的路径，剩下的就是满足条件的路径

-------------------------------------------------
我想到一种方法，可以不用树的结构，只是模拟树，先贴程序
/*从1到N的顺序入栈，输出所有出栈序列*/
#include "math.h"
#define N 4
main()
{
void init(int h[][],int a,int b,int k);
int i,j,sum,logo,h[1000][2*N+1],s[N],a,b,n;
int M=pow(2,2*N-1);/*共M条路径，每条有2*N个节点*/
/*h[i][]为第i条路径的操作序列，其中h[i][0]为一个标志，标志此序列是否满足条件，是则为1，否为0；从h[1]到h[2*N]为操作序列，1表示入栈，-1表示出栈*/
n=M;/*n为成功的序列计数*/
/*初始化标志和第一个操作，因为第一个操作必定为入栈操作*/
for(i=0;i<M;i++)
{
h[i][0]=1;/*1表示可以，0表示不可以*/
h[i][1]=1;
}/*1表示可以，0表示不可以*/
init(h,0,M-1,2);/*开始初始化第二个操作，不管是否满足条件的序列，都存入数组h中*/
/*剔除不符合要求的序列*/
j=0;/*从第0组至第M组依次检验*/
while(j<M)
{
logo=0;
sum=0;/*计算从h[][1]开始序列的和值*/
for(i=1;i<=2*N;i++)
{
sum+=h[j][i];
if(sum>N||sum<0)/*若出现入栈次数大于N，或出栈次数多于入栈次数*/
{
logo=1;
break;/*此序列埠满足条件*/
}
}
if(logo==1||sum!=0)/*sum和值表示入栈总数减出栈总数，若不为0，即入栈总数不等于出栈总数，则此序列不满足条件*/
{
h[j][0]=0;/*当前序列的标志为0，表示不满足条件*/
n--;/*总序列总数-1*/
}
j++;
}
/*输出各序列的出栈序列，s[]是临时模拟栈的，其中变量a表示栈顶(将要插入元素的位置，即栈顶元素的下一位置)，b表示将要入栈的元素*/
for(j=0;j<M;j++)
{
if(h[j][0]==1)/*若序列标志为1*/
{
a=0;b=1;
for(i=1;i<=2*N;i++)
{
if(h[j][i]==1&&b<=N)/*若序列操作为1(入栈)*/
{
s[a]=b;a++;b++;/*则入栈*/
}
if(h[j][i]==-1)/*若序列操作为1(出栈)*/
{
printf("%d",s[a-1]);/*输出出栈的元素*/
a--;/*则入栈*/
}
}
printf("\n");
}
}
printf("ALL %d !",n);/*所有序列数*/
getch();
}
/*递归初始化*/
/*从a到b前一半赋值为1，后一半赋值为-1，由此可得所有的序列*/
/*每步操作(从2到2*N步)都可以任意的为入栈，出栈，然后剔除不满足条件的序列(不满足条件包括栈中没有元素还出栈，或入栈总数超过要出栈的个数，或入栈数与出栈数步相等)，剔除的程序段在主函数中*/
void init(int h[1000][2*N+1],int a,int b,int k)
{
int i,p=a+(b-a)/2;
if(k<=2*N)
{
for(i=a;i<=p;i++)
h[i][k]=1;
for(i=p+1;i<=b;i++)
h[i][k]=-1;
init(h,a,p,k+1);
init(h,p+1,b,k+1);
}
}本回答被提问者采纳

Answer 3

你要算法，从程序中归纳就行了
我想到一种方法，可是有点复杂，要用到树的结构，先给你看个程序，是计算n个元素进栈，可能的出栈系列种数
/*递归求n个元素进栈，可能的出栈系列种数*/
#define
N
4
int
m=0,a=0,b=N;/*m表示种数，a表示栈中元素个数，b表示外面还有需要进栈的个数*/
main()
{
inS(a,b);/*首先入栈*/
printf("%d",m);
getch();
}
int
inS(int
a,int
b)/*入栈*/
{
a++;b--;/*入栈栈中元素+1，栈外元素-1
*/
if(b>0)/*若栈外有元素，可以入栈*/
inS(a,b);
if(a>0)/*若栈中有元素，可以出栈*/
outS(a,b);
}
int
outS(int
a,int
b)/*出栈*/
{
a--;/*出栈栈中元素-1*/
if(a==0&&b==0)/*若栈中元素和栈外元素都为0个*/
{
m++;/*则此种情况的序列满足条件，种数+1*/
return;
}
if(b>0)
inS(a,b);
if(a>0)
outS(a,b);
}
若想输出这些序列，可以建立一个二叉树，二叉树的节点为操作（进栈或出栈），从根节点（第一个入栈）到叶子节点（最后一个出栈）的路径就是每个序列的操作序列，每条路径共有2N个节点，分别为每个元素的入栈和出栈操作，然后通过遍历，将这些节点输出即可
建立这棵树可以用上面的递归建立，也可以用下面的方法建立
①建立一颗深度为2N的满二叉树(根节点深度为1)，其中根节点为IN（入栈），其他左子树为IN，右子树为OUT（出栈），这棵树共有2^(2N-1)个叶子节点，用根节点到叶子节点共有2^(2N-1)条路径
②保留满足下面条件的路径，其他的剔除
1)路径从根到叶出现IN和OUT总次数均为N个
2)路径从根到叶出现
IN次数≥OUT次数(即出栈次数不可能多余入栈次数)
然后输出保留的每条路径上节点类型为OUT的数据，即是出栈序列
剔除方法可由下面方法实现
1根节点赋值为1，
2节点为IN，则此节点赋值为父节点的值+1，节点为OUT，则此节点赋值为父节点的值-1，
3剔除节点的值为负数，或值>N的节点，或叶子节点上的值不=0的路径，剩下的就是满足条件的路径
-------------------------------------------------
我想到一种方法，可以不用树的结构，只是模拟树，先贴程序
/*从1到N的顺序入栈，输出所有出栈序列*/
#include
"math.h"
#define
N
4
main()
{
void
init(int
h[][],int
a,int
b,int
k);
int
i,j,sum,logo,h[1000][2*N+1],s[N],a,b,n;
int
M=pow(2,2*N-1);/*共M条路径，每条有2*N个节点*/
/*h[i][]为第i条路径的操作序列，其中h[i][0]为一个标志，标志此序列是否满足条件，是则为1，否为0；从h[1]到h[2*N]为操作序列，1表示入栈，-1表示出栈*/
n=M;/*n为成功的序列计数*/
/*初始化标志和第一个操作，因为第一个操作必定为入栈操作*/
for(i=0;i<M;i++)
{
h[i][0]=1;/*1表示可以，0表示不可以*/
h[i][1]=1;
}/*1表示可以，0表示不可以*/
init(h,0,M-1,2);/*开始初始化第二个操作，不管是否满足条件的序列，都存入数组h中*/
/*剔除不符合要求的序列*/
j=0;/*从第0组至第M组依次检验*/
while(j<M)
{
logo=0;
sum=0;/*计算从h[][1]开始序列的和值*/
for(i=1;i<=2*N;i++)
{
sum+=h[j][i];
if(sum>N||sum<0)/*若出现入栈次数大于N，或出栈次数多于入栈次数*/
{
logo=1;
break;/*此序列埠满足条件*/
}
}
if(logo==1||sum!=0)/*sum和值表示入栈总数减出栈总数，若不为0，即入栈总数不等于出栈总数，则此序列不满足条件*/
{
h[j][0]=0;/*当前序列的标志为0，表示不满足条件*/
n--;/*总序列总数-1*/
}
j++;
}
/*输出各序列的出栈序列，s[]是临时模拟栈的，其中变量a表示栈顶(将要插入元素的位置，即栈顶元素的下一位置)，b表示将要入栈的元素*/
for(j=0;j<M;j++)
{
if(h[j][0]==1)/*若序列标志为1*/
{
a=0;b=1;
for(i=1;i<=2*N;i++)
{
if(h[j][i]==1&&b<=N)/*若序列操作为1(入栈)*/
{
s[a]=b;a++;b++;/*则入栈*/
}
if(h[j][i]==-1)/*若序列操作为1(出栈)*/
{
printf("%d",s[a-1]);/*输出出栈的元素*/
a--;/*则入栈*/
}
}
printf("\n");
}
}
printf("ALL
%d
!",n);/*所有序列数*/
getch();
}
/*递归初始化*/
/*从a到b前一半赋值为1，后一半赋值为-1，由此可得所有的序列*/
/*每步操作(从2到2*N步)都可以任意的为入栈，出栈，然后剔除不满足条件的序列(不满足条件包括栈中没有元素还出栈，或入栈总数超过要出栈的个数，或入栈数与出栈数步相等)，剔除的程序段在主函数中*/
void
init(int
h[1000][2*N+1],int
a,int
b,int
k)
{
int
i,p=a+(b-a)/2;
if(k<=2*N)
{
for(i=a;i<=p;i++)
h[i][k]=1;
for(i=p+1;i<=b;i++)
h[i][k]=-1;
init(h,a,p,k+1);
init(h,p+1,b,k+1);
}
}