数据结构中出栈序列问题分析

范玉红

（沧州师范学院，河北 沧州 061000）

数据结构中出栈序列问题分析

范玉红

（沧州师范学院，河北 沧州 061000）

数据结构中的出栈序列问题是算法中一个较复杂的问题，目前，针对这个问题的解决方法有很多。文章阐述栈的定义及其出栈序列问题，以及数据结构中出栈序列问题的几种解决方法，希望对出栈序列问题的解决有一定的借鉴性意义。

数据结构；出栈序列；问题分析

随着计算机的发展，在数据结构中出栈序列问题的研究也越来越多，该问题的解决有利于促进算法的发展。目前，针对出栈序列问题已经出现了很多的解决办法，但如何使计算程序简单化是解决出栈序列问题的重点所在。本文主要分析了几种相对较简单的解决出栈序列问题的方法。

1 栈的定义及其出栈序列问题

栈作为一种数据结构，指的是只能在栈的顶部进入或被排除出去的特殊线性表。栈的头部称为栈顶，栈的尾部称为栈尾。在栈顶进入的元素一般称为进栈，从栈中被排除出去的元素一般称为出栈。因为只能在栈的顶部进入或者排除出去相关的元素，所以后进入栈的元素反而先出栈，这里又引出了栈的另一个称呼，即后进先出表。正是因为栈的这种后进先出的特点，使得栈在算法中的应用非常广泛。某一算法问题只要满足栈的这一特性，就可以利用栈来解决。因此，在解决算法问题时，理解并能有效应用栈结构就显得很有必要。在栈的研究内容中，经常被用来研究的问题是对有n个元素进入或被排除出去的栈进行研究。

具体的出栈序列问题是指，在栈顶进入或被排除出去的n个元素都满足后进先出原则，问从这n个元素中可以得到多少个出栈序列。针对这个问题的解决有很多方法，如把所有出栈序列都一一列出来，然后从中找出符合条件的出栈序列；通过将出栈序列问题转化为算法中树的排列问题来解决；利用数学中的组合知识解决出栈序列问题等。这是几种较普遍的关于出栈的序列问题的解决方法，本文着重结合自己学习的经验提出几种特别的关于出栈序列问题的解决方法，具体分析如下。

2 数据结构中出栈序列问题的几种解决办法

2.1 利用精简的计算公式来解决

前文中有提到解决出栈序列问题有一种方法是可以把所有出栈序列都一一列出来，然后再从中找出符合条件的出栈序列。这个解决方法如果放在应试考试中若遇到n比较大的情况难免会较繁琐，可以利用精简的计算公式来简化整个计算过程。

出栈序列的一般计算公式为：

具体的简化方法有以下几个步骤：（1）记住少数几个具有代表性的f（n，m）答案。若已知f（1，1）=1，f（2，2）=2，f（3，3）=5，那么就可以简化当n=4时的计算程序，我们可以列出当n=4时的计算程序，发现f（4，4）=14，这时可以总结出其中的规律，从而计算出f（n，m）的值，就算n再大也都可以通过套用公式的方法解决。（2）可以得出这样的算法规律：f（n-1，n）=f（n，n）。因为f（n，n）=f（n-1，n）+f（n，n-1），由f（n，m）的计算公式可知，只有当n的数值大于m时整个计算过程才能顺利进行，因此，可以得出，f（n，n-1）=0，这样就可以得出以上计算规律。之后就是套用该计算公式，无论n有多大，都可以快速得到答案。

2.2 利用排除法解决出栈序列问题

前文中有提到解决出栈序列问题的其中一个解决方法是利用数学中的组合知识，在具体运用时并不单纯只有这一类知识，还需要结合很多简便的数学解题技巧，如排除法。

出栈序列问题当n较大时，就会有非常多的数列组合，可以先列出其中相对简单的数列组合，然后再利用计算公式计算出n个元素时可能的数列组合。但这些数列组合并不一定都满足要求，需要符合栈的后进先出原则。可以通过一一排列来分析：

当n=1时，只有1个数列排列组合，即1，出栈的序列数也只有1个；当n=2时，有两个数列排列组合，即12 21 ，计算出的出栈序列个数也只有两个；当n=3时，有6个数列排列组合，即123 213 231 321 132 312 ，其中312这种组合方式由于不符合栈的后进先出原则，故排除掉，所以实际的出栈序列数为5个，这时出栈序列数小于数列排列组合；当n=4时，有24个数列排列组合，即1234 2134 1243 2143 1324 3214 1342 2341 3241 2431 3421 1432 4321 3124 4123 3142 4132 4213 4231 1423 4312 2413 3412，其中3124 4123 3142 4132 4213 4231 1423 4312 2413 3412不符合栈的后进先出原则，故要排除掉这10个数列组合，所以实际的出栈序列数为14个，这时出栈序列数小于数列排列组合。

通过列举以上较简单的数列组合和相应的出栈序列数，可以得出两个结论：（1）出栈序列个数小于或者等于数列组合个数；（2）当较大的数字被排在前面时，通常整个数列会以降序的形式呈现。通过以上两条观察得出的结论，推算出若n的数值大于或者等于二，减去第一位为最大数的不符合栈的原则的组合数列，剩余的符合条件的排列个数为：n×m+1（n为数列排列组合的总个数，m为第一位为最大数的不符合栈的原则的组合数列）。

当n的数值较小时，貌似列出的所有数列组合个数都可以将其归为出栈序列组合，但是当n越来越大时，不符合条件的数列组合也会越来越多，这说明想利用栈来解决算法问题必须符合栈的后进先出原则。

除了以上两个结论外，还可以推断出第3个结论，排在最前面的数字与排在它后面的小于它的数字都必须遵循降序排列的原则，另外，除第一位数字外，在后面的遵循降序排列的数字可以随意插入比第一位数字大的数字。简单来说，只有在栈的顶端的元素才能出来。针对这个结论，可以通过简单的例子来加以说明。譬如，有这样的几个数列排列方式：312 4312 4231 2413 1423 ，这几个数列都不满足栈的后进先出的原则。312这个数列组合，3排在最前面，后面的1与2应当遵循降序排列的原则，但事实上并没有；4312这个数列组合，4排在最前面，后面的数字3，1，2这几个数字应遵循降序排列方式，正确的排列方式应为4321，所以后面的4231自然也不符合条件，被排除掉；2413这个数列组合，排在最前面的是2，后面的4，3都大于2，可以随意排列，但是在4后面的数字1，3比4小，应当遵循降序排列的原则，符合条件的排列方式应为2431，所以2413不符合要求，应当被排除掉；数列组合1423之所以不符合的原因类似于2413的推断方法，这里不再一一赘述。

根据结论三，还可以推断出第4个结论，即无论是降序排列的数列组合还是升序排列的数列组合都符合栈的后进先出原则，即都是符合条件的数列组合。

事实上，只要理解了结论三，就可以写出所有的数列组合，并且可以快速地把不符合条件的删除掉。以有5个数的数列组合来具体分析：把5放在首位，那么通过结论二可以知道，只有降序排列这一种数列组合符合要求，可以根据公式得出具体的排列组合，总个数为5×4×3×2×1=120个，其中符合条件的是以降序的方式排列出来的组合，按照要求一一列举出来就可以了，这里不再一一列举。

当把4放在第一位时，放在其后的必然是5，3这两个数字，不可能是1，2。若5在第二位，后面的需以降序的方式排列，只能有一种排列方式45321；若3排在第二位，那么后面的5可任意穿插，有43521，43251，43521这3种排列方式。

由于篇幅有限，只列举出两种以5为首位和以4为首位的排列方式，以下排列方式的原理类似于这两种排列方式。

3 结语

综上所述，栈作为一种数据结构，在算法的计算中占有重要位置。本文主要阐述了栈的定义及其出栈序列问题。目前，针对出栈序列问题有很多解决方法，本文主要是结合个人学习的经验列举出两种具有代表性的解决出栈序列问题的解决方法。

[1]靳红霞，吕龙辉.数据结构中经典算法及其教学策略探讨[J].信息与电脑（理论版），2010（3）：126.

[2]吴红芝，郭麦成，吴浩.数据结构中内部排序算法的分析[J].计算机时代，2010（6）：38-39.

[3]王涛春，罗永龙，左开中.基于在线评测的数据结构实践教学探讨[J].计算机教育，2010（10）：88-91.

Analysis of stacking sequence issue in data structure

Fan Yuhong
（Cangzhou Normal University, Cangzhou 061000, China）

The stacking sequence issue in data structure is a complicated problem in the algorithm. At present, there are many methods for solving this problem. This paper elaborates the de fi nition of the stuck and stack sequence issue, and several solutions to the stacking sequence issue in data structure, hoping to have certain reference signi fi cance to solve the stack sequence issue.

data structure; stacking sequence; issue analysis

范玉红（1964— ），女，河北沧州人，本科，副教授；研究方向：计算机软件。