数据�l�构�W�三章应用题�?qi��ng)参考答案[9]_跨考网

 (t��ng) (t��ng) 1. ����q�顺序存储队列的假溢出的避免�Ҏ(gu��)���?qi��ng)队列满和空的条件。�?a target="_blank">�׃��大学 2000 一�?/span>2 (4�?/span>)�?/span>

　　【参考答案�?/span>

　　��N��序存储队列用一�l�数�l?/span>q[m]表示�Q�其�?/span>m为队列中元素个数�Q�队列中元素在向量中的下标从0�?/span>m-1。设队头指针�?/span>front�Q�队���指针是rear�Q�约�?/span>front指向队头元素的前一位置�Q?/span>rear指向队尾元素。当front�{�于-1旉����I�，rear�{�于m-1时�ؓ(f��)队满。由于队列的性质�Q�“删除”在队头而“插入”在队尾�Q�，所以当队尾指针rear�{�于m-1�Ӟ���?/span>front不等�?/span>-1�Q�则队列中仍有空闲单元，所以队列�ƈ不是真满。这时若再有入队操作�Q�会(x��)造成假“溢出”。其解决办法有二�Q�一是将队列元素向前“��^�U�Z��（占用0�?/span>rear-front-1�Q�；二是���队列看成首�������q�，卛_�@环队列（0..m-1�Q�。在循环队列下，仍定�?/span>front=rear时�ؓ(f��)队空�Q�而判断队满则用两�U�办法，一是用“牺牲一个单元”，�?/span>rear+1=front�Q�准���记是（rear+1�Q?/span>%m=front�Q?/span>m是队列容量）(j��)时�ؓ(f��)队满。另一�U�解法是“设标记”方法，如设标记tag�Q?/span>tag�{�于0情况下，若删除时��D��front=rear为队�I�；tag=1情况下，若因插入��D��front=rear则�ؓ(f��)队满�?/span>

　　2. 利用两个�?/span>sl,s2模拟一个队列时�Q�如何用栈的�q�算实现队列的插入，删除以及(qi��ng)判队�I�������。请����q�这些运���的���法思想。�?a target="_blank">北京邮电(sh��)大学 1992 一�?/span>1】�?a target="_blank">东南大学 1999 一�?/span>1 �Q?/span>7分）(j��)�?/span>

　　【参考答案�?/span>

　　栈的特点是后�q�先出，队列的特�Ҏ(gu��)��先进先出。初始时设栈s1和栈s2均�ؓ(f��)�I��?/span>

　　�Q?/span>1�Q�用�?/span>s1�?/span>s2模拟一个队列的输入�Q�设s1�?/span>s2定w��相等。分以下三种情况讨论�Q�若s1未满�Q�则元素�?/span>s1栈；�?/span>s1满，s2�I�，则将s1全部元素退栈，再压栈入s2�Q�之后元素入s1栈；�?/span>s1满，s2不空�Q�已有出队列元素�Q�，则不能入队�?/span>

　　�Q?/span>2�Q�用�?/span>s1�?/span>s2模拟队列出队�Q�删除）(j��)�Q�若�?/span>s2不空�Q�退栈，��x(ch��ng)��队列的出队；�?/span>s2为空�?/span>s1不空�Q�则��?/span>s1栈中全部元素退栈，�q�依�ơ压�?/span>s2中，s2栈顶元素退栈，�q�就是相当于队列的出队。若�?/span>s1为空�q�且s2也�ؓ(f��)�I�，队列�I�，不能出队�?/span>

　　�Q?/span>3�Q�判队空 若栈s1为空�q�且s2也�ؓ(f��)�I�，才是队列�I��?/span>

　　讨论�Q?/span>s1�?/span>s2定w��之和是队列的最大容量。其操作是，s1栈满后，全部退栈�ƈ压栈�?/span>s2�Q�设s1�?/span>s2定w��相等�Q�。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时�Q?/span>s2退栈完毕后�Q?/span>s1栈中元素依次退栈到s2�Q?/span>s2退栈完毕，相当于队列中全部元素出队�?/span>

　　在栈s2不空情况下，若要求入队操作，只要s1不满�Q�就可压�?/span>s1中。若s1满和s2不空状态下要求队列的入队时�Q�按出错处理�?/span>