oijopiogij'pj'pk'p88

先说一般结论 从初始输入序列1, 2, ..., n通过一个栈得到输出序列p1, p2, ..., pn的充分必要条件是：不存在这样的i, j, k满足i再说证明 充分条件 如果不存在这样的序列i, j, k满足i ..., pj, ..., pk, ..., pi, ... (pj 不存在这样的输出序列 ..., pi, ..., pj, ..., pk, ... （或简单地，对于输入序列123，不存在输出序列312） 从中可以看出，pi后进先出，满足栈的特点，因为pi最大，所以pi在pj和pk之后进栈，并且在pj和pk之前出栈，这同时说明在pk之前进入的pj不可能在pk之后出来，也满足先进后出的特点，所以构成一个栈。 必要条件 如果初始输入序列是1, 2, ..., n并进栈，又同时存在这一的i, j, k满足i ..., pj, ..., pk, ..., pi, ... (pj 存在这这样的输出序列： ..., pi, ..., pj, ..., pk, ... 从中可以看出，pi先进后出，满足栈的特点，然而在pk之前进入的pj却在pk之前出来，不满足先进后出的特点。因此前面假设其是栈不成立，本例得政。 原问题：《判断一个序列是不是栈的输出序列.pdf》