出栈序列的研究

Study of Out-Stack Sequence

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

Stack is a very important data structure. Recttrsion and function call cannot get away the stack. Research of the instack and the out - stack of n elements is a main content of stack. Expresses the in- stack and the out - stack sequence with binary tree, gives an algorithm＇to create a binary tree by pre - O stack sequence, proves that the number of out - stack sequence is C （2 n,n ）/（ n ＋ 1 ）when n elements put in the stack in order, analyzes and studies the three algorithms about solutions of out - stack sequence, and presents an algorithm, its time complexity is O（n） , that judges whether some sequence is out - stack sequence. Execution efficiency of the program is improved by the algorithm.