第三章 栈和队列 作业 1、若按教材P44 页图3.1（ b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： （ 1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ （ 2）如果进站的车厢序列为123456，则能否得到435612 和135426 的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列 ）。 123、 132、 213、 231、 321 输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4 个元素（4356）得到后，栈中元素剩12，且2 在栈顶，不可能栈底元素1 在栈顶元素2 之前出栈。 得到135426 的过程如下：1 入栈并出栈，得到部分输出序列1；然后2 和 3 入栈，3 出栈，部分输出序列变为：13； 接着4 和 5 入栈，5， 4 和 2 依次出栈，部分输出序列变为13542；最后6 入栈并退栈，得最终结果135426。 2、试证明：若借助栈由输入序列1、2……n得到的输出序列为p1、p2……pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，i〈 j〈 k 使 pj
pj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于i
