首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
用俩个栈模拟实现一个队列,如果栈的容量分别是O和P(OP)
[单选题]
用俩个栈模拟实现一个队列,如果栈的容量分别是
O
和
P(O>P),
那么模拟实现的队列最大容量是多少?
O+P
2O+1
2P+1
2O-1
查看正确选项
添加笔记
求解答(35)
邀请回答
收藏(1082)
分享
23个回答
添加回答
110
ZhuFG
作图不好请见谅
发表于 2019-07-24 14:52:42
回复(13)
21
drunken
两个关键点吧,一个是大栈不能一次进太多,否则影响小栈的出栈顺序;二是可以把p+2到2p+1入小栈,大栈栈底的p+1可以直接出大栈去排队
发表于 2020-08-16 11:11:41
回复(1)
12
一颗努力学习的米
可以这样理解么: 最后p和o全部出栈,不能有p+1在p前面的情况,必须保证先进先出,所以p全部出栈时是1、2...p,o比p大,我们暂且存p+1个就是从p+1...2p+1,出栈后放入p中,只能放2p+1...p+2,此时o中还剩个p+1,现在我们已经得到1..p,再将o中的p+1出栈,再将之前o压到p中的元素出栈,可以得到1...2p+1;如果o中再多存一个,存到2p+2的话,那最后o中就会剩p+2和p+1,出栈的时候p+2在p+1前面,不符合队列的先进先出了,所以最多只能到2p+1
发表于 2022-04-09 13:32:53
回复(1)
6
牛客986550360号
我的想法是先把容量小的栈即P 填满,然后再放一个元素到大栈O中,然后P中元素弹出进入O中,再把P中填满,一共是P+1+P
发表于 2022-07-25 21:48:49
回复(2)
5
香菜牛肉面加辣
<p>最重要的是通过俩个栈保持队列的先进先出特点</p><p>所以以下步骤</p><p>1⃣️1234…p进栈P 这些数再进栈O(为了先进先出)</p><p>2⃣️此时O再进p+1~2p+1</p><p>现在总容量2p+1</p><p>P中所有数出栈 O中2p+1~p+2进栈P</p><p>此时O中只有p+1 出栈 正好保持了先进先出的特点(就是为什么2p还多一个1)</p><p>P再出栈 以上就满足队列先进先出的特点</p><p><br></p>
发表于 2020-10-27 16:14:08
回复(0)
3
牛客866155151号
因为O比P容量要大,所以O>=P+1,最大容量就是他一次性可以存多少,所以刚刚开始就要先把P填满,此时为P,而要想实现先进先出,O里面最多只能存储P+1个,假设O里面有大于P+1个,因为O是借助P实现先进先出,所以O里面的元素得先进入P在输出才能实现先进先出,当P里面的原来的都输出后,然后在输出O里面的,
假如这时O里面有大于P+1个,而P里面只能存P个,而O里面最先进去的在最底部,所以不能实现先进先出。
发表于 2023-08-05 17:17:17
回复(0)
3
出土学点习。
//好像不太懂......
//如果说最小容量是(2P+1),那还能理解
发表于 2020-07-14 22:51:45
回复(4)
2
为二叉树而来
小栈存p个(1-p),大栈存(p+1-2p+1)的p+1个,将小栈的p个出栈,再将大栈的2p+1-p+2出栈,存入小栈中,小栈中的p个元素存入大栈相应位置,再出栈是从大栈开始可以有2p+1个
发表于 2022-11-02 16:59:22
回复(0)
2
鲁班六号
应该就是O中只能比p多一个元素,如果在多的话出栈顺序就不正常了
发表于 2021-04-07 17:04:44
回复(0)
1
simon_free
大栈A,小栈B,数据入大栈,先进后出,入栈再出栈后,是逆序;出完大栈入小栈,先进后出,出完小栈是正序,整个过程就是先进先出的特点,一次性存储满数据之后再出栈时,两个栈最多可以存2P+1的数据量,使其保持先进先出的特点。为什么呢,大栈出栈时,p+1不用进入小栈,直接出栈
发表于 2023-10-28 12:10:20
回复(0)
1
Von_Frins
1.将P个元素压入栈A中。此时,栈A中有P个元素,栈B为空。
2.将这P个元素从栈A中弹出并压入栈B中。此时,栈A为空,栈B中有P个元素。
3.可以从栈B中弹出一个元素,执行出队操作。此时,栈A为空,栈B中有P-1个元素。
4.可以继续将O个元素压入栈A中。此时,栈A中有O个元素,栈B中有P-1个元素。
由于栈A的容量为O,而栈B的容量为P(O > P),所以在这种情况下,模拟队列的最大容量为:
O(栈A中的元素)+ P - 1(栈B中的元素)
由于O > P,所以O = P + 1(O比P多一个容量)。代入上述等式,得到:
(P + 1) + P - 1 = 2P
这里可以再加上一个元素,因为在上述步骤3中,从栈B中弹出了一个元素。所以,最大容量为:
2P + 1
因此,当栈的容量分别为O和P(O > P)时,模拟实现的队列最大容量为2P + 1。
发表于 2023-04-24 00:08:09
回复(0)
1
GoAshore
🐴
发表于 2022-12-11 16:36:19
回复(0)
1
牛客676574203号
那是不是p栈的入栈顺序必须是p、(p-1)…1,o栈的入栈顺序必须是(p+1)、(p+2)…(2p+1),才可以让出栈的数字变成1、2……2p+1
发表于 2022-06-28 13:12:06
回复(0)
0
Pupill
第一步,元素1到p压入栈O,然后全部元素从栈O出栈压入栈P,此时这p个元素的入栈顺序是1到p;第二步,元素p+1到2p+1压入栈O,此时栈P栈O都已满;第三步,全部元素出栈,首先栈P的元素出栈顺序是1到p,然后栈O内的元素2p+1到p+2个元素全部出栈并按出栈顺序压入栈P,此时栈O内只剩p+1这个元素,直接将这个元素出栈,然后栈P中元素按顺序出栈,顺序应该是p+2到2p+1,最终可得到全部元素的出栈顺序是1到2p+1
编辑于 2024-03-21 15:40:12
回复(0)
0
牛客马MAXEY
取决于小栈P,至于那加的1是大栈里剩余一个元素的时候直接出就行
发表于 2023-11-10 15:44:56
回复(0)
0
土豆你个洋芋
为啥不是o+2p
发表于 2023-10-25 08:12:25
回复(0)
0
希望奇迹发生的回笼觉觉主很亲切
现在我看懂了c可以了,考试为什么A不行呢,不能分三次以上入p栈吗
发表于 2023-05-14 07:56:33
回复(1)
0
yfmw
原因主要在与小栈满了,大栈可以额外再放一个,然后小栈在把数据移动到大栈,所以就保持了出栈的顺序,然后小栈继续放满,所以是2p+1
发表于 2023-03-09 17:43:05
回复(0)
0
牛客962716912号
不懂哎 谁能教教我
发表于 2022-10-07 21:38:58
回复(0)
0
坚定的小猫面向对象
为啥O中可以多一个啊
编辑于 2022-09-20 17:29:51
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
栈
京东
PHP工程师
2019
上传者:
小小
难度:
23条回答
1082收藏
1822浏览
热门推荐
相关试题
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(3)
来自
职能类模拟题14
有两根粗细均匀的香,每根燃尽需1小...
京东
智力题
评论
(11)
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(2)
来自
职能类模拟题14
如果通过这次面试我们单位录用了你,...
岗位认知
自我认知
评论
(1)
请你说说Java的特点和优点,为什...
Java
评论
(273)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题