已知Q是一个非空队列 S是一个空栈。仅用队列和栈的ADT函数和少量工作变量 使用 Pascal或C语言
队列,函数,变量
已帮助 人
已知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函数有：
请帮忙给出正确答案和分析，谢谢！
-
正确答案：根据队列先进先出和栈后进先出的性质先将非空队列中的元素出队并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈依次插入初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素最后退栈的元素(出队时第一个元素)成了最后入队的元素从而实现了原队列的逆置。核心语句段如下： makempty(s)； ／／置空栈 while(!isEmpty(Q)) ／／队列Q中元素出队 {value=deQueue(Q)；push(svalue)； }
根据队列先进先出和栈后进先出的性质,先将非空队列中的元素出队,并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈,依次插入初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素,最后退栈的元素(出队时第一个元素)成了最后入队的元素,从而实现了原队列的逆置。核心语句段如下：makempty(s)；／／置空栈while(!isEmpty(Q))／／队列Q中元素出队{value=deQueue(Q)；push(s,value)；}