首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈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
80
问题
请利用两个栈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://kaotiyun.com/show/pVCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
公元9~13世纪是西欧封建庄园的兴盛时期,典型的庄园采用()的剥削方式。
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
完整地表述电磁场理论的物理学家是()。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:明朝推行一条鞭法中“一”的内容是()
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
民族区域自治制度
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
1977年4月,对“两个凡是”提出批评,开全党思想解放先河的是()。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
梁漱溟建设()学校,分为()学和()学两级。
抗战时期,文化界提出文艺创作的目标有
麻子仁丸、济川煎、增液承气汤都具有的功用是
关于公募基金的募集,以下描述正确的是()。
事务所应当对一切合理依赖或使用其出具的不实审计报告而受到损失的利害关系人承担赔偿责任,这些赔偿责任是()。
甲集团公司是ABC会计师事务所的常年审计客户,主要从事化妆品的生产、批发和零售。A注册会计师负责审计甲集团公司2014年度财务报表,确定集团财务报表整体的重要性为600万元。资料一:A注册会计师在审计工作底稿中记录了审计计划,部分内容摘录如下:(1)
备货生产是四类生产方式中的一种,对其正确的描述是:()。
内容效度的评估方法有()。
如图,在四边形ABCD中,=0,=4,则的值为()
下面的程序输出结果是()。#defineU5#defineVU+1#defineWV*V/2main(){printf("%d",W);printf("%d",5*W);}
最新回复
(
0
)