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

出栈序列相对入栈序列关系在数据结构的定义里，栈是只允许一端进行插入或删除操作的线性表。人们总结简化为后进先出原则。栈的定义给定以后引出了另一类问题出栈序列问题。就是在给定一个入栈序列（如a1,a2an）的条件下，在进栈操作时，允许出栈操作，来判断一下哪些序列是可能的出栈序列，而哪些必不是出栈序列。当然，前提是要保证要求判断的序列里面的元素要与给定入栈序列里的元素一一映射。否则就没有再往下判断的必要了。对于这类问题一般的方法是在本子上画表格模拟一个栈然后实际操作一下，看看哪些是可调度实现的，哪些是不可能实现的。这种方法是很不严谨的，而且工作量很大，对于一个具有n个元素的入栈序列，它的出栈序列有(1/(n+1)*C2nn 种可能。如果n稍大一点，工作量会颇具规模。到这来，您也许会有点被忽悠了，其实给定一个如栈序列，a1,a2,an ，再给定出要判断的出栈队列 ai ,aj , ak ,判断他们是否匹配，很简单，用一个大小为n的数组模拟栈，以a1,a2,an 做输入，对照着要判断的序列ai ,aj , ak , ，有目的的操作在线性时间内就可以完成。只是这种操作人工来说稍微麻烦一点罢了。对于人工做判断，研究发现这类问题是具有一般规律的。在此先给出这一定律的定义，然后举几个常见的应用，最后给出证明。这一定律是：在给定入栈顺序序列的前提下，对于其出栈序列里任意元素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开头的序列个数是多少个？这一问题是可以很方便用上面给的规律来解决。序列以元素d开头说明d是第一个出栈的。a,b,c要晚于d出栈同时a,b,c对先于d入栈，所以根据上面的规律a,b,c,d的排列顺序只能是dcba。除了元素d 的前面e还可以有4个位置可取，所以答案是4种。3. 给定一个正整数元素序列 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）以所给的次序依次进栈，在进栈操作时，允许出栈操作。则判断另一个已知序列元素一一映射序列记为Sb可否成为原序列的充分必要条件是：对于序列Sb里的任意元素ak，相应于Sa里排在其前面的且在Sb里排在其后面的所有元素按与Sa对应相反的顺序排列。已知序列Sk,x1,x2xi,xn(iI且1=i=n)对于任意三个整数1=ijk=n有Nixjxk假设序列里有一元素xi，其右面的小于其元素值的元素不都严格递减即存在j,kijmax(xj,xk)XiXk可知这三个元素既不符合xixjxk,即也与题设矛盾，由此可知，结论正确。必要性证明：对于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,a3an-1,an,对映抽象为1,2,3，n-1,n（数值越大，表示其排列越靠后，即入栈越晚）记为Sd。对于序列Sb,x1,x2,x3, ,xn,里面的元素与Sd一一映射，且xi的下标值i的大小代表其在Sb的位置情况，数值越大越靠后，即出栈越晚。如果对于任意三个整数1=ijk=n,xi,xj,xk满足xixjxk（即如果ximax（xj,xk）必须同时有xixk）。来讨论一下。我们以I代表入栈操作。0代表出栈操作。当ximax(xj,xk)时，1）假设xi,xj,xk相邻，即k-j=j-i=1xi,xj,xk三个元素大小关系全排列有3！=6种，这里符合要求的有四种分别为xixj,xixk,xjxk x的对应值由小到大排列 xixjxkxixj,xixk xixkxjxixk,xjxk xkxixj,xixk,xjxk xjxixk因为x的值与Sd里面的整数是一一映射关系，而Sd里面的整数是Sa里面相对位置上的元素是一一对应的。所以xi,xj,xk的大小关系就是他们所对应的，整数所对应的Sa里面的元素的位置关系。可根据以上分析可求得xi,xj,xk所间接对应到的Sa里元素的位置关系。以xi,xj,xk表示其间接对应元素，可得以上四种情况分别的入栈顺序。而且我们都可以让他们经过栈后实现xi,xj,xk的排列xi,xjxk 对应出栈入栈操作方法IxiOxiIxjOxjIxkOxkxi,xkxjIxiOxiIxkIxjOxjOxkxk,xixjIxkIxiOxiIxjOxjOxkxj,xixkIxjIxiOxiOxjIxkOxk所以，如果ximax(xj,xk)且xi,xj,xk相邻，我们是可以调度期间接对应到的Sa内的元素来实现符合相应顺序的出栈序列。2）假设xi,xj,xk不都相邻xixjxk在ximax(xj,xk)的前提下，他们的大小关系还是有以上那四种情况。xixjxkxixkxjxkxixjxjxixk它们的间接对应元素为xi xj xk xi xk xj xk xi xj xj xi xk 在保证除xixjxk以外的元素正确调度的前提下，我们依然可以按Ixi Oxi Ixj Oxj Ixk Oxk Ixi Oxi Ixj Oxj Ixk Oxk Ixk Ixi Oxi Ixj Oxk Oxk Ixj Ixi Oxi Oxj Ixk Oxk 的调度方法保证其实现xi xj xk的排列。所以如果xi 当xixjxk时（即，ximax(xj,xk)，则xjxk）1） 假设xi,xj,xk相邻，即k-1=j-i=1分别以xi,xj,xk表示xi,xj,xk的间接对应元素，由xixjxk可知它们的入栈顺序是：Xkxj,xi可以由IxkIxjIxiOxiOxjOxk来实现出栈序列按xi,xj,xk排列。所以知，如果xixjxk且xixjxk相邻，可以调度其间接对应到Sa的元素，以固定顺序入栈得到xixjxk的出栈序列。2） 当xi,xj,xk不都相邻时xixjxk在xixjxk的前提下保证其它元素可正确调度，还可以按Ixk Ixj Ixi Oxi Oxj Oxk 得到xi xj xk的出栈序列。所以，如果xixjxi,不论xi,xj,xk相邻与否，都可以调度其间接对应到Sa内的元素，