首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈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
58
问题
请利用两个栈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
学硕统考专业
相关试题推荐
下列各项内容和王羲之的书法成就有关的是()。①开始把字体由隶书转化为楷书②书法代表作有《兰亭序》、《黄庭经》等③他博彩众长,世称“书圣”④其子王献之书法造诣也极高,父子合称“二王”
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
若一个栈的输入序列为1,2,3…n,输出序列的第一个元素是i,则第j个输出元素是()。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
在某个操作系统中,通过大量的实验,人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比,即可用内存加倍,缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns,但若发生了缺页中断就需要1ms。一个程序运行了60s,期
随机试题
设有直线,则该直线【】
ResearchershavefoundthatREM(rapideyemovement)sleepisimportanttohumanbeings.Thistypeofsleepgenerallyoccursfour
下列哪项是风湿性心脏瓣膜病水气凌心射肺证(以苓桂术甘汤合葶苈大枣泻肺汤治疗)的治法
A.粗死亡率B.年龄别死亡率C.标准化死亡率D.平均预期寿命E.婴儿死亡率为比较年龄结构不同的人群整体死亡水平,可采用
A.最小有效量B.最小中毒量C.治疗量D.极量E.半数致死量出现疗效所需的最小剂量
开放式基金的注册登记体系的模式包括()。I.“混合”模式Ⅱ.基金管理人自建注册登记系统的“外置”模式Ⅲ.委托中国证券登记结算公司作为注册登记机构的“外置”模式Ⅳ.基金管理人自建注册登记系统的“内置”模式
Thetraditionalmarketsretaintheir______forthemanyChinesewhostillpreferfreshfoodlikelivefish,ducks,chickensover
计算并填写下表:【2】
Whatwasitoriginallycalled?
Theoceanbottom—aregionnearly2-5timesgreaterthanthetotallandareaoftheearth—isavastfrontierthateventodayisl
最新回复
(
0
)