3.6试证明,若借助栈由输入序列123.n得到的输出序 列为p1p2…pn(它们是输入的一个排列),则在输出序列 中不可能出现这样的情形:存在<j<k使 pj<pk<pi 证明 根据i<j<k得出栈次序pi、pj、pk 又根据pj<pk<pi,所以pj、pk、pi入栈的次序依此 为:pj、pk、pi,由于pi最先出栈,此时的p、pk必在栈中, 且形式是p在下、pk在上,得出栈次序pi、pk、pj。 所以由<j<k和 pj<pk< pi推导出互相矛盾的结果,故原 命题成立。3.6 试证明，若借助栈由输入序列１２３…n得到的输出序 列为p1p ２ ….p n （它们是输入的一个排列），则在输出序列 中不可能出现这样的情形：存在i < j < k使pj<pk<pi. 证明: 根据 i < j < k 得出栈次序pi、pj、pk。 又根据 pj < pk < pi，所以 pj、pk、pi入栈的次序依此 为：pj、pk、pi，由于pi最先出栈，此时的 pj、pk必在栈中， 且形式是pj在下、pk在上，得出栈次序pi、 pk 、 pj 。 所以由i < j < k和pj<pk<pi推导出互相矛盾的结果，故原 命题成立