问答题
已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有： makeEmpty(S：stack)； ／／置空栈 push(S：stack；value：datatype)； ／／新元素value进栈 pop(S：stack)：datatype； ／／出栈，返回栈顶值 isEmpty(S：stack)：Boolean； ／／判栈空否 队列的ADT函数有： enQueue(q：queue：value：datatype)； ／／元素value进队 deQueue(q：queue)：datatype； ／／出队列，返回队头值 isEmpty(q：queue)：boolean； ／／判队列空否【清华大学2000六(12分)】【华南理工大学2005二、7(4分)】
【正确答案】正确答案：根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素(出队时第一个元素)成了最后入队的元素，从而实现了原队列的逆置。核心语句段如下： makempty(s)； ／／置空栈 while(!isEmpty(Q)) ／／队列Q中元素出队 {value=deQueue(Q)；push(s，value)； } ／／将出队元素压入栈中 while(!isEmpty(s)) ／／栈中元素退栈 {value=pop(s)； enQueue(Q，value)；) ／／将出栈元素入队列Q
【答案解析】