问答题 利用两个栈s1、s2模拟一个队列时,如何用栈的运算实现队列的插入、删除以及判队空运算。请简述这些运算的算法思想。【北京邮电大学1992一、1】【东南大学1999一、1(7分)】
【正确答案】正确答案:栈的特点是后进先出,队列的特点是先进先出。初始时设栈s1和栈s2均为空。(1)用栈s1和s2模拟一个队列的输入:设s1和s2容量相等。分以下三种情况讨论:若s1未满,则元素入s1栈;若s1满,s2空,则将s1退栈到空,退栈元素依次压栈入s2,之后元素入s1栈;若s1满,s2不空(已有出队列元素),则不能入队。(2)用栈s1和s2模拟队列出队(删除):若栈s2不空,退栈,即是队列的出队;若s2为空且s1不空,则将s1栈中全部元素退栈,并依次压入s2中,s2栈顶元素退栈,这就是相当于队列的出队。若栈s1为空并且s2也为空,队列空,不能出队。(3)判队空:若栈s1为空并且s2也为空,才是队列空。讨论:s1和s2容量之和是队列的最大容量。其操作是,s1栈满后,全部退栈并压栈入s2(设s1和s2容量相等)。再入栈s1直至s1满。这相当于队列元素“入队”完毕。出队时,s2退栈完毕后,s1栈中元素依次退栈到s2,s2退栈完毕,相当于队列中全部元素出队。在栈s2不空情况下,若要求入队操作,只要s1不满,就可压入s1中。若s1满和s2不空状态下要求队列的入队时,按出错处理。
【答案解析】