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

Research on and Implementation of an Out-Stack Sequence

作　　者：姜华林[1] 李立新[2] 陈强[2] JIANG Hua-lin,LI Li-xin,CHEN Qiang（1.Zunyi Vocational and Technical College,Zunyi 563000,China;2.Southwest University,Chongqing 400715,China）

机构地区：[1]遵义职业技术学院,贵州遵义563000 [2]西南大学,重庆400715

出　　处：《电脑知识与技术》2013年第3期1578-1581,共4页Computer Knowledge and Technology

摘　　要：栈是一种非常重要且特殊的数据结构,任何递归和函数调用都离不开栈。研究n个元素的进栈与出栈性质是栈的主要研究内容。该文在出栈序列深入分析和研究的基础上,针对某一序列是否为合法出栈序列的问题,提出了一种基于三元素出栈序列索引的时间复杂度为O（n2）的新算法。该算法简单易懂并且比其他传统判断方法具有更高的效率。A stack is a very important and special data structure.Any function call can not be separated from the stack.Research on the in-stack and the out-stack of n elements is a main content.The character of out-stack sequence is analyzed and re searched in this paper and a new algorithm is proposed for judging a sequence whether it is a rational out-stack sequence.The al gorithm is based on the three-element-index of out-stack sequence and its time complexity is O（n2）.The algorithm is simple and easy to understand and more efficiency than the other traditional method.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]