首页 > 试题广场 >

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

[单选题]
用俩个栈模拟实现一个队列,如果栈的容量分别是OP(O>P),那么模拟实现的队列最大容量是多少?
  • O+P
  • 2O+1
  • 2P+1
  • 2O-1
栈:先进先出
队列:先进后出
问题可以转换为:在装入N个元素时,出栈时依然满足先进先出,但在装入N+1个元素时,不再满足先进先出的逻辑。
解: 大的栈作为存储站,小的栈作为缓冲栈;栈O 装入栈P容易的元素,为了使得这些元素先进先出,必须将这些元素压如缓冲栈,再从缓冲栈pop
发表于 2019-08-24 13:55:30 回复(2)
https://www.cnblogs.com/eniac12/p/4865158.html
发表于 2019-05-25 20:25:11 回复(0)
答:栈A的容量为O,栈B的容量为P,由于O>P,则A为存储栈,B为缓存区
1.将1,..,P元素入栈A,栈底到栈顶的顺序为P,...,1,然后A栈弹出,依次入栈B,然后输出1,,..P
2.将P+1,...,2P+1元素入栈A,然后依次弹出2P+1,...,P+2共n个元素,然后依次入栈B,栈A弹出输出P+1,栈B依次弹出P+2,..,2P+1元素
实现队列容量为2P+1

发表于 2019-05-30 22:40:49 回复(0)
剑指offer上有相关问题来解释怎么模拟,这里就说一下为什么是2P+1,假设现在p满了,o没有满,接着往o里面push,最后o也满了,想pop,这个时候需要先pop p里面的,这部分是没有问题的,p空了之后,把o的要搬到p中去,可是p的容量比o小,导致最后进来的o-p个元素是装不下的
发表于 2019-07-27 08:46:37 回复(2)