我要招人

去企业版

首页 > 试题广场 >

用俩个栈模拟实现一个队列，如果栈的容量分别是O和P(OP)

[单选题]

用俩个栈模拟实现一个队列，如果栈的容量分别是O和P(O>P)，那么模拟实现的队列最大容量是多少？

```
O+P
```
```
2O+1
```
```
2P+1
```
```
2O-1
```

查看正确选项

ZhuFG

作图不好请见谅

发表于 2019-07-24 14:52:42 回复(12)

drunken

两个关键点吧，一个是大栈不能一次进太多，否则影响小栈的出栈顺序；二是可以把p+2到2p+1入小栈，大栈栈底的p+1可以直接出大栈去排队

发表于 2020-08-16 11:11:41 回复(1)

一颗努力学习的米

可以这样理解么：最后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)

牛客986550360号

我的想法是先把容量小的栈即P 填满，然后再放一个元素到大栈O中，然后P中元素弹出进入O中，再把P中填满，一共是P+1+P

发表于 2022-07-25 21:48:49 回复(2)

香菜牛肉面加辣

最重要的是通过俩个栈保持队列的先进先出特点所以以下步骤1⃣️1234…p进栈P 这些数再进栈O（为了先进先出）2⃣️此时O再进p+1～2p+1现在总容量2p+1P中所有数出栈 O中2p+1～p+2进栈P此时O中只有p+1 出栈正好保持了先进先出的特点（就是为什么2p还多一个1）P再出栈以上就满足队列先进先出的特点

发表于 2020-10-27 16:14:08 回复(0)

牛客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)

为二叉树而来

小栈存p个（1-p），大栈存（p+1-2p+1）的p+1个，将小栈的p个出栈，再将大栈的2p+1-p+2出栈，存入小栈中，小栈中的p个元素存入大栈相应位置，再出栈是从大栈开始可以有2p+1个

发表于 2022-11-02 16:59:22 回复(0)

出土学点习。

//好像不太懂......

//如果说最小容量是(2P+1)，那还能理解

发表于 2020-07-14 22:51:45 回复(3)

simon_free

大栈A,小栈B,数据入大栈，先进后出，入栈再出栈后，是逆序；出完大栈入小栈，先进后出，出完小栈是正序，整个过程就是先进先出的特点，一次性存储满数据之后再出栈时，两个栈最多可以存2P+1的数据量，使其保持先进先出的特点。为什么呢，大栈出栈时，p+1不用进入小栈，直接出栈

发表于 2023-10-28 12:10:20 回复(0)

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)

GoAshore

🐴

发表于 2022-12-11 16:36:19 回复(0)

牛客676574203号

那是不是p栈的入栈顺序必须是p、（p-1）…1，o栈的入栈顺序必须是（p+1）、（p+2）…（2p+1），才可以让出栈的数字变成1、2……2p+1

发表于 2022-06-28 13:12:06 回复(0)

鲁班六号

应该就是O中只能比p多一个元素，如果在多的话出栈顺序就不正常了

发表于 2021-04-07 17:04:44 回复(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)