首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈sl和s2来模拟一个队列。已知栈的三个运算定义如下: (1)push(st,x):元素x入st栈: (2)pop(st,x):st栈顶元素出栈,赋给变量x; (3)sempty(st):判st栈是否为空。 那么如
请利用两个栈sl和s2来模拟一个队列。已知栈的三个运算定义如下: (1)push(st,x):元素x入st栈: (2)pop(st,x):st栈顶元素出栈,赋给变量x; (3)sempty(st):判st栈是否为空。 那么如
admin
2019-08-15
82
问题
请利用两个栈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
学硕统考专业
相关试题推荐
《中国国民党改组宣言》发表的时间是()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
某激光打印机每分钟打印20页,每页4000字符,相应的设备驱动程序一次输出一个字符,采用中断方式,CPU处理每次中断需50微秒,则CPU用于打印的开销是()。
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法),分析其死锁的可能性并提出解决方案。Philosopheri:d0{wait(chopstick[i];wait(ch
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
设有一个带头结点的循环单链表,其结点值均为正整数。试设计一个算法,反复找出单链表中结点值最小的结点,并输出之,然后将该结点从中删除,直到单链表空为止,最后再删除表头结点。
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
在下面的应用中,通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值
随机试题
整体式向心滑动轴承装配时对轴套的检验除了测定圆度误差及尺寸外,还要检验轴套孔中心线对轴套端面的()。
A.桶状胸B.扁平胸C.鸡胸D.漏斗胸E.肋骨串珠胸骨下部显著前凸,两侧肋骨凹陷,此种胸廓称为
据相关部门统计,中国2010年全年国内生产总值300000亿元,经济增长率为8.0%,这也是自2003年以来首次增长率低于9%,下列关于经济增长率的说法中正确的是()。
某基金会共有理事21人。一天,该基金会召集理事会会议,投票决定基金会在上海设立分支机构的议案。当天仅有17名理事到会。那么,至少需要()名理事投赞成票,设立分支机构的议案才可以通过。
A、 B、 C、 D、 A
安全电子邮件使用()协议。
用scanf("%d,%d",&a,&b)输入数据时,下面输入法中,正确的是______。
Humanlikeanimalbehaviorhasastrikingeffect.Dogsandeatsbolsterourmoraleandmakeusfeelspecial,becausetheyofferu
A、Anapartmentoncampus.B、Anapartmentwithfurniture.C、Anapartmenttoherself.D、Anapartmentfarfromthetraffic.B女士说她希望
A、It’ssunny.B、Friday.C、Ilikeit.D、December9th.A本题是询问天气如何,B是星期几,D是日期,C与题意无关,而A是晴天,故选A。
最新回复
(
0
)