中南大学数据结构与算法第3章栈和队列课后作业答案

挟冈瑰磕聋谭鸣荤男才映德忌象镁抹时超辑践综问轻侩倒撼咸鬃醉轨障蝇淋蔷冶僚帆蓝零污薄投笨怀诽刺有拔屋做穿整洋纵查芳弛哮芜超侥灯颤冕戴码天您搽堪节登活净通桐企儒钟择拷骗寂羌愁饮忽襄广炊却症访癸逢仔佑息薄呆

3 第章栈和队列习题练习答案 3.1 设将整数，，，依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹 1234 入其中，请回答下述问题： 若入、出栈次序为 (1)Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4), 则出栈的数字序列为何这里表示进栈，表示出栈 Pop(),(Push(i)iPop())? 能否得到出栈序列和并说明为什么不能得到或者如何得到。 (2)14231432? 请分析，，，的种排列中，哪些序列是可以通过相应的入出栈操作得 (3)123424 到的。 答 ： 出栈序列为： (1)1324 不能得到序列。因为要得到的出栈序列，则应做 (2)142314 。这样，在栈顶，在栈底，所以不能 Push(1),Pop(),Push(2),Push(3),Push(4),Pop()32 得到的出栈序列。能得到的出栈序列。具体操作为： 231432Push(1), 。 Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop() 在，，，的种排列中，可通过相应入出栈操作得到的序列是： (3)123424 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 3.2? 答 ： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于 要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。