首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈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
60
问题
请利用两个栈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月,清政府颁布(),规定皇帝具有至高无上的权力。
“两个凡是”
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
编写判定给定的二叉树是否是二叉排序树的函数。
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
在西方社会,一提到黑人,很多人马上会想到愚蠢、落后、原始等观念,这些偏见属于态度的()
A.α受体B.β1受体C.β2受体D.M受体E.N受体导致支气管平滑肌舒张的肾上腺素能受体是
男性,20岁,间断活动后气短3年,加重伴有双下肢水肿2个月。儿童时曾患“心肌炎”。查体:BP100/50mmHg,双下肺可闻及细湿啰音,心界向两侧扩大,心率90次/分,律齐,心音低钝,肝肋下4cm,双下肢可凹性水肿。超声心动:全心扩大,左室舒张末内径70m
A.白内障囊外摘除术后晶状体后囊膜浑浊B.反复发作色素膜炎引起晶状体浑浊C.角膜穿通伤后晶状体前囊膜破裂、晶状体浑浊D.出生时即存在晶状体局限性浑浊E.出生6个月时发现晶状体局限性浑浊外伤性白内障
牡丹皮的气味为( )。
人民教师整个职业道德体系的显著特征是()。
为帮助大学生树立科学的消费观,推动年轻人群信用意识升级和诚信体系建设,团中央、教育部、银监会等多部门联合发起“金融安全专家校园行”活动。王先生是互联网金融服务公司L集团的运营官,作为活动嘉宾来到M大学,在活动现场向近300名学生宣讲信用安全的重要
()一个孩子的智龄越大,说明他的智力发展水平越好。
设A=有三个线性无关的特征向量,求x,y满足的条件.
121.191.255.255
最新回复
(
0
)