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