如何判断出栈序列的合法性?

规则是：出栈序列中的每个数后面的比它小的数，是按递减排列的。

简化规则描述：

1、假设入栈顺序为1234。

1）若出栈序列为4123，显然不满足上述要求，因为对于4，它后面比它小的数字序列为123，而123是一个递加系列即不是递减排列，所以不是合法出栈序列。      

2）若出栈系列为3142，也不合法，因为3后面比它小的1和2不是递减排列的。      

3）若出栈系列为1234，则合法，因为对于每一个数字它后面没有比它小的数字。    

2、假设入栈顺序为123456789abcdef。      

1）若出栈系列为67d51f94e2ba83c，因为对于d，它后面比它小的19或123或ac等等都不是递减的，所以不合法。      

2）若出栈系列为379a8b65c4ed21f，可以证明是合法的出栈顺序。因为对于每一个数字它后面没有比它小的数字而且是按递减排列的。 

3、证明：

假设入栈顺序为1234......n，可知在栈中的元素从栈顶到栈底一定是按严格递减排列的,而且每个数i进栈之前,比i小的数一定已经进栈了。

所以比i小的数要不然已经出栈,要不然在栈中，如果还在栈中则一定在i的下面，按严格递减排列,如此可见如果比i小的数还在栈中则一定在i之后输出,所以输出序列中在i后面的比i小的数一定按严格递减排列.否则出栈系列不合法。

扩展资料：

1．进栈（PUSH）算法

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

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

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

2．退栈（POP）算法

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

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

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

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

回复 DAWN_KR 的帖子首先的前提是进栈一定是要按照顺序进栈如1、2、3、4的顺序，如果第一个出的是4，那么要依次先进栈1、2、3、4，然后出栈，这样的话第一个是4，没有其他的元素可以再进栈了，所以只能按顺序出栈，这样出栈的顺序就是4、3、2、1。假如出栈的顺序是3、4、2、1，你就要先分析出3的情况，只有先将1、2、3入栈，然后将3出栈。然后进栈4，再出栈4、2、1.再如如果出栈的顺序是3、2、4、1或3、2、1、4，先将1、2、3入栈，再出栈3、2，如果这个时候是前面的序列，就先进4，再出栈4、1，如果是后面的出栈顺序就出1，然后再入栈4，再出栈4，这样就会得到上面的序列了。不知道我有没有理解LZ的意思，LZ应该问的就是这类问题吧！

这个序列对应着一个PUSH和POP组成一序列，PUSH和POP组成的序列中，在任意位置i，push的个数必须大于或等于POP~类似于一个01序列中0的个数一定要多于1的个数

出栈是后进先出，仔细体会，慢慢分析 你可以的

我也知道类似这样的序列,但具体于一个入栈和出栈序列如何判断还是找不到方法.如入栈序列1234,一个非法出栈序列是4312,如何用01序列标记它们并计算出非法的呢?