资源描述：
《出栈序列合法性研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、出栈序列合法性研究与实现摘要：栈是一种非常重要且特殊的数据结构，任何递归和函数调用都离不开栈。研究n个元素的进栈与出栈性质是栈的主要研究内容。该文在出栈序列深入分析和研究的基础上，针对某一序列是否为合法出栈序列的问题，提出了一种基于三元素出栈序列索引的时间复杂度为0(n2)的新算法。该算法简单易懂并且比其他传统判断方法具有更高的效率。关键词：栈；数据结构；出栈序列；三元素索引；算法中图分类号：TP311文献标识码：A文章编号：1009-3044(2013)07-1578-04已知一个元素为n(n彡3，ny。定义3兀素a进栈表不为a+,出栈表不为a-。定义4元素a0
2、，al，a2进栈与出栈的整个过程称为栈序列，记为R(c0,cl,c2,c3,c4,c5),其中ci表示某个元素进栈或者出栈。例如，“abc”为进栈序列，“bac”为出栈序列，则其栈序列为“a+b+bn+c-”即“a进栈b进栈b出栈a出栈c进栈c出栈”，R(c0,cl,c2,c3,c4,c5)={abc}U{bac}o性质1已知一个元素为n(n彡3)的进栈序列S(a0,al,a2,•••,an-1),其某一置换为T(bO,bl,b2,…，bn-1）,则任取T（bO,bl,b2,…，bn_l）中三个元素可得相应的三元素出栈序列索引J（x，y，z）。性质2如果元素aO，
3、al，a2按序进栈，aO的进栈序号称为“前”记为P，al的进栈序号称为“中”记为N，a2的进栈序号称为“后”记为L（该性质便于出栈序列判断的直观理解）。性质3如果元素aO，al，a2按序进栈，其出栈序列共有5种可能，也对应J（X，y，z）中x、y和z的5种关系，具体为：1）PNL（前中后），xx>z；4）NPL（中前后），yy〉z;定理1J（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
4、〉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（aO,al，a2，…，an-1）的任一出栈序列为T（bO，bl，b2，…，bn-1），那么序列T（b
5、O,bl，b2，…，bn-1）中不存在LPN（后前中）的这样一个三元素非法出栈序列索引r（X，y，Z）o由定理1可证。推论2如果一个元素为n（n彡3）的序列T（bO，bl，b2，…，bn-1）是进栈序列S（aO，al，a2，…，an-1）的某一合法出栈序列，那么必然存在栈序列R（cO,cl，c2,…，cn-1）,R（cO，cl，c2，…，cn~l）=S（aO，al，a2，…，an-1）UT（bO，bl，b2，…，bn-l）o由推论1和定义4可证。2出栈序列判断算法该算法核心思想是在要判断的出栈序列T（bO,bl,b2，…，bn-1）中查找是否存在LPN（后前中）的
6、这样一个三元素非法出栈序列索引J’（X，y，Z），若存在则该出栈序列非法，反之为合法出栈序列。具体操作步骤如下：1）将出栈序列T（bO,bl,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-l，反复执行此步直至j=0,然后i=i-l,
7、执行第3）步；5）j=j-l,如果出栈索引数组第个j元素的值大于z,则将出栈索引数组第个j元素的值赋给三元素出栈序列索引J（x,y,z）中的X，执行第7）步；否则j=j_l，反复执行此步直至j
