若借助栈由输入序列1,2…n得到的输出序列为p1p2…pn(它是输入序列的一个排列)，证明在输出序列中不可能出现这样的情形：存在着i<j<k使pj<pk<pi
因为输入序列是从小到大排列的，所以若pj<pk<pi，则可以理解为通过输入序列pj，pk，pi可以得到输出序列pi，pj，pk，显然通过序列123是无法得到312的。所以不可能存在着i<j<k使pj<pk<pi
