利用两个栈s1 s2模拟一个队列时 如何用栈的运算实现队列的插入 删除以及判队空运算。请简述这些运
队列,两个,北京
已帮助 人
利用两个栈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为空并
栈的特点是后进先出,队列的特点是先进先出。初始时设栈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为空并