判断一个序列是不是栈的输出序列

Question

如题所述

Answer 1

先说一般结论

从初始输入序列1, 2, ..., n通过一个栈得到输出序列p1, p2, ..., pn的充分必要条件是：不存在这样的i, j, k满足i<j<k同时pj<pk<pi。

再说证明

充分条件

        å¦‚果不存在这样的序列i, j, k满足i<j<k同时pj<pk<pi，即对于输入序列：

                ..., pj, ..., pk, ..., pi, ... (pj<pk<pi)

        ä¸å­˜åœ¨è¿™æ ·çš„输出序列

                ..., pi, ..., pj, ..., pk, ...

        ï¼ˆæˆ–简单地，对于输入序列123，不存在输出序列312）

        ä»Žä¸­å¯ä»¥çœ‹å‡ºï¼Œpi后进先出，满足栈的特点，因为pi最大，所以pi在pj和pk之后进栈，并且在pj和pk之前出栈，这同时说明在pk之前进入的pj不可能在pk之后出来，也满足先进后出的特点，所以构成一个栈。

必要条件

        å¦‚果初始输入序列是1, 2, ..., n并进栈，又同时存在这一的i, j, k满足i<j<k且pj<pk<pi，及对输入序列：

                ..., pj, ..., pk, ..., pi, ... (pj<pk<pi)

        å­˜åœ¨è¿™è¿™æ ·çš„输出序列：

                ..., pi, ..., pj, ..., pk, ...

        ä»Žä¸­å¯ä»¥çœ‹å‡ºï¼Œpi先进后出，满足栈的特点，然而在pk之前进入的pj却在pk之前出来，不满足先进后出的特点。因此前面假设其是栈不成立，本例得政。