首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈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
88
问题
请利用两个栈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
学硕统考专业
相关试题推荐
国共十年对峙时期,以毛泽东为代表的中国共产党人之所以能开创出以农村包围城市的中国革命道路,其主要依据是()。
1908年8月,清政府颁布(),规定皇帝具有至高无上的权力。
()是清中叶扬州画家的著名代表,他们既不墨守成规,又不脱离优秀传统,成为我国绘画艺术史上的一个新流派。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
拿内存加上外存容量之和与虚拟存储空间相比,其大小关系是()。
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
设有一个由正整数组成的无序(后向)单链表,编写能够完成下列功能的算法:(1)找出最小值结点,且打印该数值。(2)若该数值为奇数,则将其与直接后继结点的数值交换。(3)若该数值为偶数,则将其直接后继结点删除。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
随机试题
依据《火灾统计管理规定》,这起事故构成()火灾。《消防火灾事故情况表》(D1表),由()在每月15日前报送上月的事故统计报表。
Itseemsthatpoliticiansaroundtheworldarethinkingaboutthehealthoftheircountries.WhileinChina,ChenZhuhasannoun
Usinganticipatory"it":Theyarelikelytosucceed.
属于意外性移动的是
在侦查阶段,犯罪嫌疑人甲不可以行使的诉讼权利有:犯罪嫌疑人甲认为公安机关对其拘留超过法定期限,公安机关则认为对甲的拘留没有超过法定期限,下列何种观点是正确的?
关于毒品犯罪,下列哪些选项是正确的?(2016年卷二61题)
因比赛需要,模拟沙盘队的老师决定从本队的3位女性(王欣、李玲、孙梅)和5位男性(张军、金磊、吴鹏、孟飞、余星)中组建沙盘小组参加北京大学生模拟沙盘大赛,选择条件如下:①小组成员既要有男性,也要有女性;②张军和王欣不能都入选;③李玲和孙梅不能都入选;
劳动界(复旦大学2013年研;陕西师范大学2007年研)
Dolphinsarenottheonlyanimals(31)humansthatusesoundsinanapparentlyintelligentmanner.Whalesalsouseacomplexsys
YoucanalwaysdependuponJohn(be)______therewhenheisneeded.
最新回复
(
0
)