先说一般结论
从初始输入序列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之前出来，不满足先进后出的特点。因此前面假设其是栈不成立，本例得政。