首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请利用两个栈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
75
问题
请利用两个栈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
学硕统考专业
相关试题推荐
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
二次大战后,主要资本主义国家经历了增长时期,首先开始这个进程的国家是()。
公车上书后,由维新派和翰林院侍读学士文廷式发起成立的,以挽救时局为宗旨的组织是()。
简述大化改新的内容和影响。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
随机试题
走行于视神经管内的结构除视神经外,还有下列哪项
某儿童食用杏仁后出现头晕、头痛、恶心、呕吐、轻度呼吸困难,入院急救处理。上述特效药的作用机制是()。
饮大量清水后尿量增多的最主要原因是
大叶性肺炎一般起病急,寒战高热、胸痛、咳痰较黏稠或为典型红色泡沫痰。()
对建设项目应予进行敏感性分析的因素包括()。
把地球划分成东、西两半球的经线圈是:
李强是个不太诚实的人,他可以随时欺骗某些人。若上述论述为真,那么以下哪些判定必然为真()(1)你随时都可能被李强欺骗(2)李强随时都可能欺骗人(3)因为李强是个不太诚实的人,所以他会随时想着欺骗人(4)我有可
ThekeytotheindustrializationofspaceistheU.S.spaceshuttle.【C1】______it,astronautswillacquireaworkhousevehicle【C
Thechangesinlanguagewillcontinueforever,butnooneknowssure【M1】_____.whodoesthechanging.Onepossibilityis
A、Theadvantagesoftraditionalsurveyingmethods.B、Usingsatellitestocommunicatewithmountainclimbers.C、Obtainingnewinf
最新回复
(
0
)