本文格式为Word版，下载可任意编辑出栈序列相对入栈序列关系 出栈序列相对入栈序列关系 在数据布局的定义里，栈是只允许一端举行插入或删除操作的线性表人们总结简化为后进先出原那么栈的定义给定以后引出了另一类问题——出栈序列问题就是在给定一个入栈序列（如a1,a2…an）的条件下，在进栈操作时，允许出栈操作，来判断一下哪些序列是可能的出栈序列，而哪些必不是出栈序列当然，前提是要保证要求判断的序列里面的元素要与给定入栈序列里的元素一一映射否那么就没有再往下判断的必要了 对于这类问题一般的方法是在本子上画表格模拟一个栈然后实际操作一下，看看哪些是可调度实现的，哪些是不成能实现的这种方法是很不严谨的，而且工作量很大，对于一个具有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. fedcba B. bcafed C. dcefba D. 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对应相反的依次排列 递减 即存在j,k imax(xj,xk) Xixj>xk 假设序列里有一元素xi，其右面的小于其元素值的元素不都严格 可知这三个元素既不符合xixj>xk,即也与题设冲突，由此可知，结论正确 必要性证明：对于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,对映抽象为1,2,3，…，n-1,n（数值越大，表示其排列越靠后，即入栈越晚）记为Sd 对于序列Sb,x1,x2,x3, …,xn,里面的元素与Sd一一映射，且xi的下标值i的大小代表其在Sb的位置处境，数值越大越靠后，即出栈越晚假设对于任意三个整数1xj>xk（即假设xi>max（xj,xk）务必同时有xi>xk）来议论一下我们以I代表入栈操作0代表出栈操作 当xixk xixk,xj>xk xkxj,xi 当xi>xj>xk时（即，xi>max(xj,xk)，那么xj>xk） 1） 假设xi,xj,xk相邻，即k-1=j-i=1分别以xi’,xj’,xk’表示xi,xj,xk的间接对应元素，由xi>xj>xk可知它们的入栈依次是： Xk’xj’,xi’可以由Ixk’Ixj’Ixi’Oxi’Oxj’Oxk’来实现出栈序列按xi’,xj’,xk’排列。
所以知，假设xi>xj>xk且xixjxk相邻，可以调度其间接 对应到Sa的元素，以固定依次入栈得到xi’xj’xk’的出栈序列 2） 当xi,xj,xk不都相邻时 …xi…xj…xk… 在xi>xj>xk的前提下保证其它元素可正确调度，还可以按 …Ixk’ …Ixj’ …Ixi’ …Oxi’ …Oxj’ …Oxk’ … 得到…xi’ …xj’ …xk’的出栈序列 所以，假设xi>xj>xi,不管xi,xj,xk相邻与否，都可以调 度其间接对应到Sa内的元素，以固定依次入栈，而得到…xi’ …xj’ …xk’ …的出栈序列 综合1,2可知对于已知的入栈序列到Sa，a1,a2, …an,序列Sb里面的元素与Sa一一映射假设Sb里的任意元素ak，相应于Sa里排在ak前面，且在Sb里排在ak后面的全体元素，按与在Sa里的相反依次排列，就可以断定Sb里Sa的入栈序列 综述可知，这是个充要条件 — 6 —。