Question

一个栈的输入序列是12345，则栈的输出序列有哪几种？

把各种序列列出来

Answer 1

一个栈的输入序列是12345，则栈的输出序列只有一种为54321。

栈作为一种数据结构，只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。因此，一个栈的输入序列是12345，栈的输出序列也只有一种为54321。

扩展资料：

在计算机系统中，栈具有动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。

栈在程序的运行中有着举足轻重的作用。栈可以用来在函数调用的时候存储断点，做递归时要用到栈。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。

Answer 2

序列个数太多，以123为例：123进栈，出栈321；1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,所以是123，以此类推。

则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1)

此时m>=1, 因为必须栈中有元素才可以出栈

当m=0则(n,0)的问题只能转化为(n-1,1)

当问题为(0, m)时得到递归边界，这个问题的解是只有一种排列

最终推导的结果是：P2n ＝ C（n 2n）— C（n＋1 2n）=C（n 2n)/(n+1)

这个结果是一个“卡塔兰数”Catalan,在组合数学中有介绍,可以参阅有关资料

结果=C(5,10)/6= 42

扩展资料：

1、进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

②置TOP=TOP+1（栈指针加1，指向进栈地址）；

③S(TOP)=X，结束（X为新进栈的元素）；

2、退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；

②X=S(TOP)，（退栈后的元素赋给X）：

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

参考资料来源：百度百科-栈

Answer 3

序列个数太多了，还是以123为例吧：
123进栈，出栈321
1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,所以是123
以此类推。

追问

还是不会啊，，，我是完全不懂的那种

追答

1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,所以是123
1进栈,2进栈,2出栈,1出栈,3进栈,3出栈,所以是213
1进栈,2进栈,2出栈,3进栈,3出栈,1出栈,所以是231
1进栈,2进栈,3进栈,3出栈,2出栈,1出栈,所以是321
输入序列是123的输出序列就这4中情况；
输入序列是12345的输出序列是12345 12435 12453 12543 21345 21435 21543 23451 23541 24531 25431 32451 32541 34521 35421 43215 43251 43521 45321 54321；
为什么出栈顺序没有31... 42...? 当3先出的时候，1和2已经在栈里了结合已知的进栈顺序，1不可能比2先出来。自己再琢磨一下就明白了。

Answer 4

Answer 5

int Train_into_PlatForm(int i) // i是序列的长度 12345长度是5
{ int j=0;
if(i==0) return 1;
else
if(j==0) return Train_into_PlatForm(i-1,1);
else return Train_into_PlatForm(i-1,j+1)+Train_into_PlatForm(i,j-1);
}
去试试吧
输入5输出是42