出栈序列的研究

• 作者: 徐亚平 李红卫
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 出栈序列 Catalan数 二叉树
• 年，卷（期）: 2007,（10）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 127-129,133
• 页数: 4页
• 分类号: TP311.12
• 字数: 3048字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2007.10.036

摘要

栈是一种非常重要的数据结构,递归、函数调用都离不开栈.对n个元素入栈和出栈的研究是栈的一个主要研究内容.利用二叉树给出了入栈和出栈序列的表示;给出了由前置O栈序列构造出二叉树的算法;证明了对于按次序入栈的n个元素,其出栈序列总数为C(2n,n)/(n+1);对三种求解出栈序列算法进行了分析和研究,并提出一种时间复杂度为O(n)判断某一序列是否为出栈序列的算法,它提高了程序的执行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐亚平	江苏技术师范学院计算机科学与工程学院	10	94	7.0	9.0
2	李红卫	江苏技术师范学院计算机科学与工程学院	20	70	5.0	7.0