出栈序列合法性研究与实现

姜华林　李立新　陈强

摘要：栈是一种非常重要且特殊的数据结构，任何递归和函数调用都离不开栈。研究n个元素的进栈与出栈性质是栈的主要研究内容。该文在出栈序列深入分析和研究的基础上，针对某一序列是否为合法出栈序列的问题，提出了一种基于三元素出栈序列索引的时间复杂度为O（n2）的新算法。该算法简单易懂并且比其他传统判断方法具有更高的效率。

关键词：栈；数据结构；出栈序列；三元素索引；算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）07-1578-04

已知一个元素为n（n≥3，n<3时结果很显然，因此不必研究）的进栈序列设为S（a0，a1， a2，…，an-1），再设T（b0，b1， b2，…，bn-1）为进栈序列S（a0，a1， a2，…，an-1）的一个置换，则T（b0，b1， b2，…，bn-1）是否为一个合法的出栈序列是一个值得深入研究的问题。文献[1～7]对其相关问题进行了分析和研究。对此文献[2]给出了一个算法思想简单但时间复杂度较高（O（n3））的判定算法；文献[6]给出了一个基于栈的判断算法，它通过对入栈、出栈操作的反演得出判断，其时间复杂度虽然较低（为O（n2）），但它没有分析出栈序列本身具有的特性[7]；文献[7]提出了一种基于降序段的时间复杂度为O （n2）的算法但仍然较为复杂。该文对出栈序列性质进行了进一步的分析和研究，在此基础上提出了一种基于三元素出栈序列索引的新方法，该方法可以快速有效地判定T（b0，b1， b2，…，bn-1）是否为一个合法的出栈序列，给出了一种更为优化的算法实现；同时根据栈的性质利用非栈算法实现了对元素为n（n≥3）的进栈序列S（a0，a1， a2，…，an-1）的进栈与出栈模拟。

1 问题分析

为了便于问题描述引入三元素出栈序列索引J（x，y，z）。

定义1 J（x，y，z）中x，y，z分别表示某个元素进栈的索引序号，J（x，y，z）表示x对应元素最先出栈，y对应元素第二出栈，z对应元素最后出栈。

定义2 J（x，y，z）中如果x对应元素比y对应元素先进栈，则称为xy。

定义3 元素a进栈表示为a+，出栈表示为a-。

定义4 元素a0，a1，a2进栈与出栈的整个过程称为栈序列，记为R（c0，c1，c2，c3，c4，c5），其中ci表示某个元素进栈或者出栈。例如，“abc”为进栈序列，“bac”为出栈序列，则其栈序列为“a+b+b-a-c+c-”即“a进栈b进栈b出栈a出栈c进栈c出栈”，R（c0，c1，c2，c3，c4，c5）={abc}∪{bac}。

性质1 已知一个元素为n（n≥3）的进栈序列S（a0，a1， a2，…，an-1），其某一置换为T（b0，b1， b2，…，bn-1），则任取T（b0，b1， b2，…，bn-1）中三个元素可得相应的三元素出栈序列索引J（x，y，z）。

性质2 如果元素a0，a1，a2按序进栈，a0的进栈序号称为“前”记为P，a1的进栈序号称为“中”记为N，a2的进栈序号称为“后”记为L（该性质便于出栈序列判断的直观理解）。

性质3 如果元素a0，a1，a2按序进栈，其出栈序列共有5种可能，也对应J（x，y，z）中x、y和z的5种关系，具体为：

1）PNL（前中后），x

2）PLN（前后中），x

3）NLP（中后前），y>x>z；

4）NPL（中前后），y

5）LNP（后中前），x>y>z；

定理1 J（x，y，z）中如果x>z>y，则称J（x，y，z）为三元素非法出栈序列索引，特记为J（x，y，z）。

证

1）根据定义1，设x对应元素为ai，设y对应元素aj，设z对应元素ak，出栈序列为ai、aj、ak；

2）根据定义2和条件x>z>y，则三元素进栈序列为：aj、ak、ai；

由上可知，元素ai是最先出栈的，同时ai是最后进栈的，这说明在ai进栈之前aj和ak已经进栈但没有出栈，而aj比ak先进栈，那么根据栈的先进后出性质可知，aj必然比ak后出栈，反之假设aj比ak先进栈，同时aj比ak先出栈，那么aj必然是最先出栈的元素，这与ai是最先出栈的元素相矛盾，所以出栈序列ai、aj、ak为非法出栈序列，该J（x，y，z） 为三元素非法出栈序列索引。

推论1 如果一个元素为n（n≥3）的进栈序列S（a0，a1， a2，…，an-1）的任一出栈序列为T（b0，b1， b2，…，bn-1），那么序列T（b0，b1， b2，…，bn-1）中不存在LPN（后前中）的这样一个三元素非法出栈序列索引J（x，y，z）。

由定理1可证。

推论2 如果一个元素为n（n≥3）的序列T（b0，b1， b2，…，bn-1）是进栈序列S（a0，a1， a2，…，an-1）的某一合法出栈序列，那么必然存在栈序列R（c0，c1， c2，…，cn-1），R（c0，c1， c2，…，cn-1）= S（a0，a1， a2，…，an-1）∪T（b0，b1， b2，…，bn-1）。

由推论1和定义4可证。

2 出栈序列判断算法

该算法核心思想是在要判断的出栈序列T（b0，b1， b2，…，bn-1）中查找是否存在LPN（后前中）的這样一个三元素非法出栈序列索引J（x，y，z），若存在则该出栈序列非法，反之为合法出栈序列。具体操作步骤如下：

1）将出栈序列T（b0，b1， b2，…，bn-1）中的每一个元素的进栈序号存入出栈索引数组；

2）设i，j为计数器，i初值为出栈索引数组的长度减1，j初值为i减1；

3）如果i >1，将出栈索引数组第个i元素的值赋给三元素出栈序列索引J（x，y，z）中的z，否则执行第6）步；

4）如果出栈索引数组第个j元素的值小于z，则将出栈索引数组第个j元素的值赋给三元素出栈序列索引J（x，y，z）中的y，执行第5）步；否则j=j-1，反复执行此步直至j=0，然后i=i-1，执行第3）步；

5）j=j-1，如果出栈索引数组第个j元素的值大于z，则将出栈索引数组第个j元素的值赋给三元素出栈序列索引J（x，y，z）中的x，执行第7）步；否则j=j-1，反复执行此步直至j<0，然后i=i-1，执行第3）步；

6）算法结束，出栈序列为合法出栈序列；

7）算法结束，出栈序列为非法出栈序列。

时间复杂度为O（n2） 。

算法的关键源码如下（C#）：

1）置所有元素进栈标识为0，置栈序列为空；

2）依次扫描第i个出栈序号，若出栈序号与进栈序号一致，执行3），否则执行5）；

3）若当前序号对应元素进栈标识不为0，执行4），否则该元素加入栈序列，模拟该元素进栈，同时置进栈标识为1，执行4）；

4）当前序号对应元素加入栈序列，模拟该元素出栈，执行6）；

5）将比当前序号小的所有序号所对应元素加入栈序列，模拟所有对应元素进栈，同时置所有进栈标识为1，执行3）；

6）若出栈序号已经扫描完成，执行7），否则i=i+1，执行2）；

7）结束，返回栈序列。

算法的关键源码如下（C#）：

4 结束语

本文深入研究出栈序列合法性的规律后，在进栈序列所有元素任意排列的序列中抽象出三元素出栈序列索引J（x，y，z），根据三元素出栈序列索引J（x，y，z）的特性确定了三元素非法出栈序列索引J（x，y，z），用C#语言实现了基于三元素出栈序列索引的时间复杂度为O（n2）的新算法。该算法简单易懂并且比其他传统判断方法具有更高的效率。同时利用非栈算法实现了对元素为n（n≥3）的出栈序列T（b0，b1， b2，…，bn-1）的进栈与出栈模拟，由此推论2得到了验证。下一步，将继续对栈的性质进行深入研究，探讨栈在其他应用领域中的高效算法。

参考文献：

[1] 卢开澄.组合数学[M]. 2版.北京：清华大学出版社，1991：119-130.

[2] 徐凤生.出栈序列的性质及其求解新算法[J].计算机工程与应用，2006，42（5）：66-68.

[3] 严蔚敏，吴伟民.数据结构：C语言版[M].北京：清华大学出版社，1997：152-155.

[4] 唐保祥.栈序列及其生成算法[J].郑州大学学报：自然科学版，2001，33（4）：33-35.

[5] 范年柏，张大方，颜学义，等.基于栈操作的用例规模的一个计算公式[J].湖南大学学报：自然科学版，2004，31（6）：80-82.

[6] 李红卫，徐亚平.出栈序列的研究[J].计算机技术与发展，2007，17（10）：127-129.

[7] 吴福英，谭罗生，黄超.一个判定出栈序列的新方法[J].江西师范大学学报：自然科学版，2011（3）：251-253.