首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下: (1)push(st,x):元素x入st栈; (2)pop(st,x):st栈顶元素出栈,赋给变量x: (3)sempty(st):判st栈是否为空。 那么如
请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下: (1)push(st,x):元素x入st栈; (2)pop(st,x):st栈顶元素出栈,赋给变量x: (3)sempty(st):判st栈是否为空。 那么如
admin
2019-08-01
43
问题
请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下:
(1)push(st,x):元素x入st栈;
(2)pop(st,x):st栈顶元素出栈,赋给变量x:
(3)sempty(st):判st栈是否为空。
那么如何利用栈的运算来实现该队列的三个运算:
(1)enqueue:插入一个元素入队列;
(2)dequeue:删除一个元素出队列:
(3)queue_empty:判队列为空。
(请写明算法的思想及必要的注释。)
选项
答案
栈的特点是后进先出,队列的特点是先进先出。所以,用两个栈sl和s2模拟一个队列时,s1作输入栈,逐个元素压栈,以此模拟队列元素的入队。当需要出队时,将栈s1退栈并逐个压入栈s2中,s1中最先入栈的元素,在s2中处于栈顶。s2退栈,相当于队列的出队,实现了先进先出。显然,只有栈s2为空且s1也为空,才算是队列空。 (1)int enqueue(stack s1,elemtp x){ //s1是容量为n的栈,栈中元素类型是elemtp。本算法将x入栈, //若入栈成功返回1,否则返回0 if(top1==n&&!sempty(s2)) //top1是栈s1的栈顶指针,是全局变量 {printf(“栈满”);return(0);} //s1满s2非空,这时s1不能再入栈 if(top1==n&&sempty(s2)) //若s2为空,先将s1退栈,元素再压栈到s2 {while(!sempty(s1)){pop(s1,x);push(s2,x);} push(s1,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(s1,x);push(s2,x);} pop(s2,x); //s2退栈相当于队列出队 printf(“出队元素”,x); } (3)int quelle_empty(){ //本算法判用栈s1和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://jikaoti.com/ti/0LGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:明朝推行一条鞭法中“一”的内容是()
真理标准问题大讨论
全国高校院系调整的时间是()。
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
全国高校院系调整的具体时间是()。
1918年美国总统威尔逊提出“十四点原则”,内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。
《中国国民党改组宣言》发表的时间是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
随机试题
Arepasswordsout-of-date?Itisstartingtoseemlikeit.Everybodyhatesthem.ThesedaysatypicalInternetuserhasdozenso
王维《山居秋暝》:__________,莲动下渔舟。
A.2.0~3.0mmol/LB.2.25~2.75mmol/LC.3.5~5.5mmol/LD.6.5~7.5mmol/LE.7.5~8.5mmol/L血清钙的正常值为()
传染病近期诊断有价值的抗体是
关于经济分析与财务分析的区别,表述错误的是()。
根据骨牌理论提出的防止事故措施是()。
张某等3人共同出资设立一普通合伙企业,实缴出资比例为1:2:3。张某在执行合伙事务时因重大过失造成合伙企业负债。已知合伙协议未约定合伙企业亏损分担比例,合伙人之间也不能通过协商达成一致。关于合伙企业不能清偿的剩余债务的承担方式,下列表述正确的是()
CRT的施测时间长度是()分钟。
只有在民主、互动和相互关爱的氛围中,才能形成真正的合作学习。()
双关,是指在一定的语言环境中,利用词的多义或同音的条件,有意使语句具有双重意义,言在此而意在彼的一种修辞手法。利用词的同义,有意使语句具有双重意义叫作意义双关:利用词的同音,有意使语句具有双重意义叫作谐音双关。根据上述定义,下列选项中,运用了谐音双关修辞手
最新回复
(
0
)