出栈序列相对入栈序列关系

《出栈序列相对入栈序列关系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、出栈序列相对入栈序列关系在数据结构的定义里，栈是只允许一端进行插入或删除操作的线性表。人们总结简化为后进先出原则。栈的定义给定以后引出了另一类问题——出栈序列问题。就是在给定一个入栈序列（如a1,a2…an）的条件下，在进栈操作时，允许出栈操作，来判断一下哪些序列是可能的出栈序列，而哪些必不是出栈序列。当然，前提是要保证要求判断的序列里面的元素要与给定入栈序列里的元素一一映射。否则就没有再往下判断的必要了。对于这类问题一般的方法是在本子上画表格模拟一个栈然后实际操作一下，看看哪些是可调度实现的，哪些是不可能实现的。这种方法是很不严谨的，而且工作量很大，对于一个

2、具有n个元素的入栈序列，它的出栈序列有(1/(n+1))*C2nn种可能。如果n稍大一点，工作量会颇具规模。到这来，您也许会有点被忽悠了，其实给定一个如栈序列，a1,a2,……an，再给定出要判断的出栈队列ai,aj,ak,……判断他们是否匹配，很简单，用一个大小为n的数组模拟栈，以a1,a2,……an做输入，对照着要判断的序列ai,aj,ak,……，有目的的操作在线性时间内就可以完成。只是这种操作人工来说稍微麻烦一点罢了。对于人工做判断，研究发现这类问题是具有一般规律的。在此先给出这一定律的定义，然后举几个常见的应用，最后给出证明。这一定律是：在给定入栈顺序

3、序列的前提下，对于其出栈序列里任意元素an，晚于其出栈且先于入栈的元素必须按入栈的逆序排列。先后几个应用实例：1.设a,b,c,d,e,f以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为：A.fedcbaB.bcafedC.dcefbaD.cabdef答案是D.因为A.B.C项都满足规律，但D项里a,b晚于c出栈且先于c入栈，它们的排列顺序应是ba。2.元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留，可出栈，直到所有元素都出栈，则在所有可能出栈序列中，以元素d开头的序列个数是多少个？这一问题是可以很方便用上面给的规律来解决

4、。序列以元素d开头说明d是第一个出栈的。a,b,c要晚于d出栈同时a,b,c对先于d入栈，所以根据上面的规律a,b,c,d的排列顺序只能是dcba。除了元素d的前面e还可以有4个位置可取，所以答案是4种。1.给定一个正整数元素序列1,2,3,…,99,100.允许进栈，退栈操作交替进行，我们根据已给的规律很容易判别。1,2，…，7,10,3,11,12,6，…，97,98,99,100不是出栈序列，因为7,3,6.不符合规律。下面给出定律的证明。假设给定一个元素序列a1,a2,a3,…,an（记为Sa）以所给的次序依次进栈，在进栈操作时，允许出栈操作。则判断另

5、一个已知序列元素一一映射序列记为Sb可否成为原序列的充分必要条件是：对于序列Sb里的任意元素ak，相应于Sa里排在其前面的且在Sb里排在其后面的所有元素按与Sa对应相反的顺序排列。已知序列Sk,x1,x2…xi,xn(i∈I且1<=i<=n)对于任意三个整数1<=ixj>xk假设序列里有一元素xi，其右面的小于其元素值的元素不都严格递减即存在j,kimax(xj,xk)Xixj>xk,即也与题设矛盾，由此可知，结论正确。必要性证明

6、：对于Sa里的任意三个元素，ai,aj,ak，它们在Sa里的排列顺序是ai,aj,ak,如果在Sb里的排列顺序变为ak,ai,aj，假设序列Sb是Sa的出栈序列。根据栈的性质，和ai,aj,ak三个元素分别在Sa和Sb里的位置关系克制，为ak在栈顶时，ai,aj一定在栈里，是aj比ai更靠近栈顶。根据Sb里ak,ai,aj的位置关系知Sk是先出栈的如果ak出栈后，ai先于aj出栈，这与栈只允许在一端进行插入或删除的操作自相矛盾。充分性证明：对于序列Sa我们只关心其序列里各元素的对应位置关系，不考虑其它属性。为表述方便我们把元素a1,a2,a3…an-1,an,

7、对映抽象为1,2,3，…，n-1,n（数值越大，表示其排列越靠后，即入栈越晚）记为Sd。对于序列Sb,x1,x2,x3,…,xn,里面的元素与Sd一一映射，且xi的下标值i的大小代表其在Sb的位置情况，数值越大越靠后，即出栈越晚。如果对于任意三个整数1<=ixj>xk（即如果xi>max（xj,xk）必须同时有xi>xk）。来讨论一下。我们以I代表入栈操作。0代表出栈操作。<1>当xi

8、全排列有3！=6种，这里符合要求的有四