首页 > 试题广场 > 用俩个栈模拟实现一个队列,如果栈的容量分别是O和P(O>
[单选题]
用俩个栈模拟实现一个队列,如果栈的容量分别是OP(O>P),那么模拟实现的队列最大容量是多少?
  • O+P
  • 2O+1
  • 2P+1
  • 2O-1
栈,先进后出;队列,先进先出。用O和P这两个栈实现先进先出就可以了。
发表于 2019-07-17 16:45:55 回复(1)
保证入队完毕之后才可以出队; 
分析:栈的特点是“后进先出(LIFO)”,而队列的特点是“先进先出(FIFO)”。用两个栈模拟实现一个队列的基本思路是:用一个栈作为存储空间,另一个栈作为输出缓冲区,入队时把元素按顺序压入两栈模拟的队列,出队时按入队的顺序出栈即可。

如下图,用容量为m(较大的)的栈作为存储空间,容量为n的栈作为输出缓冲区,先将入队的前n个元素push进存储空间栈

随后对存储空间栈中的每个元素进行出栈(pop)操作,继而压入(push)输出缓冲区栈,如下图所示

对于剩余入队的前n+1个元素,将他们压入存储空间栈,两个栈的状态如下图:

此时已经入队了2n+1个元素,若此时进行出队操作,先将输出缓冲区栈中的元素出栈(pop)并输出:Q1,Q2,……,Qn,再对存储空间栈中的n个元素进行出栈(pop)并压入输入缓冲区栈,状态图如下:

然后对存储空间栈进行一次出栈(pop)操作并输出:Qn+1,最后再对输出缓冲区栈中的所有元素进行出栈(pop)操作并输出Qn+2,Qn+3,……,Q2n,Q2n+1。这样两个栈总的输出序列为:Q1,Q2,……,Qn,Qn+1,Qn+2,Qn+3,……,Q2n,Q2n+1,符合队列“先进先出”的特性,模拟成功。

但是如果前面蓝字的假设不成立,即在已经入队了2n+1个元素的情况下,还要继续向队列中添加更多的元素,将无法满足按入队的顺序出队。

综上所述,两个栈所模拟的队列的最大容量为2n+1。
--------------------- 
作者:阿特密斯X 
来源:CSDN 
原文:https://blog.csdn.net/qq_42194192/article/details/82723949 
版权声明:本文为博主原创文章,转载请附上博文链接!
发表于 2019-05-26 20:03:33 回复(0)
当出现最大容量时,P:存p个(1,2,3,,...,n)              O:存p+1个(n+1,,...,2n,2n+1)
出队列顺序需要:P出栈-P中压入剩余n个数据-O中出栈剩余的一个元素-P全部出栈:
1、P中先出p个(1,2,3,...,n) 
2、O中p个依次压入P(2n+1,2n,...,n+2)
3、O出剩余1个(n+1)
4、P中最后出p个(n+2,n+3,..,2n+1)
发表于 2019-08-08 15:25:59 回复(0)
P:存p个              O:存p+1个
出队列对应于:
1、P中先出p个, 
2、O中p个压入P,
3、O出剩余1个,
4、P中最后出p个
发表于 2019-07-29 16:01:35 回复(0)
因为O>P 这个是解题关键
发表于 2019-08-08 15:17:42 回复(0)
用容量为P+1的栈A作为存储,容量为P的栈B作为输出,先将入队的前P+1个元素进A
随后对A中的P个元素进行出栈操作,继而压入B中,A中还剩一个元素
(容量为P+1,输出时,先输出A中的剩余一个元素,再输出B中的P个元素,能保证顺序不变;如果容量大于P+1,输出顺序会发生错乱)
输出A中还剩下的一个元素,A空,B还剩P个元素
A入栈P+1个元素
总的还有P+P+1个元素
个人拙见
编辑于 2019-08-05 13:28:40 回复(0)
  • 大的作为存储栈,小的作为输出栈,这样可以存最多。

  • 瓶颈是小栈,输出栈可以一次表示两倍P,即自己的P和存储栈的P

  • +1:除了2P之外,存储栈中还能多存一个元素,因为唯一性,当第二个P进输出栈时,剩余的一个1也可以认为是有序,并且这一个多出来的1是在1P全部出栈输出,而Q中的2P进P栈后,不进P栈,直接输出的,因为第二批进栈的元素中,最先进栈的位于栈底,图示特例可以很清晰得知,不过这个不重要,这题也没考到这个点。

编辑于 2019-07-28 16:46:13 回复(0)
这题应该是求队列最大容量值中的最小值吧
发表于 2019-07-19 15:21:53 回复(0)