合法栈输出队列的充要条件

问题背景

Algorithm 4th (Robert Sedgewick, Kevin Wayne) 一书中有这样一道习题：

1.3.46 Forbidden triple for stack generability. Prove that a permutation can be gener- ated by a stack (as in the previous question) if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b).

翻译成中文，可以理解为：请证明：如果一个栈的出栈顺序合法，当且仅当不存在这样的 forbidden triple：在序列中编号 c 后有编号 a、b，其中 c和a， a和b可以有间隔，而且 a < b < c。

定理描述

对于任意一个栈，假设其入栈编号分别从 1 到 n，其出栈顺序编号分别为 p1 到 pn。那么

一个合法的出栈顺序编号当且仅当对任意的 pm (m >= 1 且 m < n)，从 pm+1开始，所有小于 pm 的子串严格单调递减。

这个定理通俗的描述是，一个合法的出栈顺序，对于任意一个编号，随后所有小于这个编号的部分是严格单调递减的。反过来也成立。

例如，下面这个入栈序列

1 2 3 4 5

的一个两个出栈序列

1. 3 2 1 5 4
2. 3 1 2 5 4

第一个是合法的，第二个是不合法的，因为比编号 3 小的随后的两个数 1 2 是递增的。

算法的证明

本文仅给出一个简略的证明方法。假设在出栈过程中，在某一个步骤时，栈中存留的元素有 n 个，分别是 s1 到 sn。

此时，对于元素 sn，有两种可能性。

1）在下一步时，可以选择弹出 sn。那么，比 sn 小的所有元素，只有两种可能：

a. 还未出栈（不可能还未入栈，因为比它大的元素 sn 已经入栈了）：则一定在 sn 后以递减的顺序出现在出栈队列中（因为入栈的顺序是严格递增的）

b. 已经出栈：此时，比这个元素还小的元素如果还没出栈，当它即将出栈的时候，就会又递归回到1）的情况。

2）可以不弹出 sn 而是继续入栈，则又回到 1）的情况。

综上所属，对于这个元素 sn，其后续元素一定是单调递减的。

原书的证明

原书给出的部分证明如下。

Partial solution: Suppose that there is a forbidden triple (a, b, c). Item c is popped before a and b, but a and b are pushed before c. Thus, when c is pushed, both a and b are on the stack. Therefore, a cannot be popped before b.

更多的证明和参考材料

栈序列及其生成算法（郑州大学学报）Vol33，No 4，Dec 2001

关于栈输出序列的问题补充