请利用两个栈sl和s2来模拟一个队列。已知栈的三个运算定义如下： (1)push(st，x)：元素x入st栈： (2)pop(st，x)：st栈顶元素出栈，赋给变量x； (3)sempty(st)：判st栈是否为空。那么如

admin2019-08-15 51

问题请利用两个栈sl和s2来模拟一个队列。已知栈的三个运算定义如下：
(1)push(st，x)：元素x入st栈：
(2)pop(st，x)：st栈顶元素出栈，赋给变量x；
(3)sempty(st)：判st栈是否为空。
那么如何利用栈的运算来实现该队列的三个运算：
(1)enqueue：插入一个元素入队列；
(2)dequeue：删除一个元素出队列；
(3)queue_empty：判队列为空。
(请写明算法的思想及必要的注释。)

选项

答案栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，sl作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈项。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。 (1)int enqueue(stack sl，elemtp x){ ／／sl是容量为n的栈，栈中元素类型是elemtp。本算法将X入栈，／／若入栈成功返回1，否则返回0 if(topl==n&&!sempty(s2)) ／／topl是栈s1的栈顶指针，是全局变量 {printf(＂栈满＂)；return(0)；} ／／sl满s2非空，这时s1不能再入栈 if(topl==n&&sempty(s2)) ／／若s2为空，先将sl退栈，元素再压栈到s2 {while(!sempty(s1)){pop(sl，X)；push(s2，x)；} push(sl，x)；return(1)；／／x入栈，实现了队列元素的入队 } (2)void dequeue(stack s2，s1){ ／／s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队 if(!sempty(s2)) ／／栈s2不空，则直接出队 {pop(s2，x)；printf(＂出队元素为＂，x)；} else ／／处理s2空栈 if(sempty(s1)){printf(＂队列空＂)；exit(0)；} ／／若输入栈也为空，则判定队空 else ／／先将栈s1倒入s2中，再做出队操作 {while(!sempty(s1)){pop(sl，x)；push(s2，x)；} pop(s2，x)；／／s2退栈相当于队列出队 printf(”出队元素”，x)； } (3)im queue—empty(){ ／／本算法判用栈sl和s2模拟的队列是否为空 if(sempty(s1)&&sempty(s2))return(1)；／／队列空 else return(0)；／／队列不空 } 提示：算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少(只要不空)，就要全部倒入s2中。

解析

转载请注明原文地址:https://kaotiyun.com/show/jOCi777K

本试题收录于：计算机408题库学硕统考专业分类

0

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)