【更新解释】用有限个栈实现队列，队列操作最坏常数时间

看晕了

原答案写得很好了。楼主可以联想一下《计算机系统结构》Tomasulo算法里保留站的作用。解决该问题的算法的核心思想就是备份和缓冲，这里我做一个简单的总结。 两个栈可以模拟队列操作。这时入队时间复杂度O(1),最坏情况下出队时间复杂度O(N)。 所以我们只需要研究如何降低出队的时间复杂度即可。 三个栈是在两个栈的基础上增加了一个出栈缓冲区H'，基本思路是当H（模拟出队操作的栈）空的时候，将缓冲区H’与H进行交换，这样可使出队复杂度降为O(1)。但只在没有数据入栈的情况下才可以这样做。（注意，如果有新的元素入栈，会破坏数据原有的先后顺序） 为了使入队的元素不破坏原有数据的顺序，这些“后来”的入队元素，我们需要额外增加一个输入缓冲栈T'进行存储。 那么，四个栈可以解决所有的问题么，不可以。因为当且仅当H和T同时为空的时候，我们才可以用H'和T'与他们交换。 现在我们考虑这样一种情况，T已经空了，H还没空，如果我们继续执行缓冲区与I/O区的交换动作，我们会失去H中的所有数据，解决这个问题的办法是再额外增加一个HR缓冲区，用以保存这些数据。这时候我们已经有五个栈了。 这里出现了一个新的问题，把H中的数据复制到HR的这段时间里，是不能进行出队操作的（H始终是模拟出队操作的栈）。 我们需要在复制的同时也能执行出队操作。解决办法是引入一个“虚栈”h，h是H的浅拷贝，用于指示复制进行之前的H的栈顶。 至此，六个栈可以完美解决队列的模拟问题。 更详细的介绍与理论证明请移步原文及《算法第四版》。

https://www.cnblogs.com/ikesnowy/p/7157813.html

感觉他所有的例子都没有讨论各种分支，只是就着一个分支讲到底，没太懂如果H为空T不为空要怎么办，引入第五个栈之前好像没有讨论。 以及即使有HR之后，H还是不为空，有什么性质约束吗 【 在 gungnir 的大作中提到: 】 : 原答案写得很好了。楼主可以联想一下《计算机系统结构》Tomasulo算法里保留站的作用。解决该问题的算法的核心思想就是备份和缓冲，这里我做一个简单的总结。 : 两个栈可以模拟队列操作。这时入队时间复杂度O(1),最坏情况下出队时间复杂度O(N)。 : 所以我们只需要研究如何降低出队的时间复杂度即可。 : ...................

【 在 lance6716 的大作中提到: 】 : 感觉他所有的例子都没有讨论各种分支，只是就着一个分支讲到底，没太懂如果H为空T不为空要怎么办，引入第五个栈之前好像没有讨论。 : 以及即使有HR之后，H还是不为空，有什么性质约束吗 你是不是被国内的算法书荼毒了……解决复杂问题不都是从特殊到一般，逐步建立完善模型的么…… 为什么不会出现H比T先空的情况，人家原文后面给证明了，感觉你没仔细看……

确实没看到，等我自己整理一遍 【 在 gungnir 的大作中提到: 】 : 你是不是被国内的算法书荼毒了……解决复杂问题不都是从特殊到一般，逐步建立完善模型的么…… : 为什么不会出现H比T先空的情况，人家原文后面给证明了，感觉你没仔细看……

原始论文思路清晰，相比之下依次解释6个栈的作用还解释的不完备的这篇博客真是囫囵吞枣，而且还使用了要求的栈操作更底层的操作（所谓的浅拷贝） 我自己写了一篇解释 https://github.com/lance6716/algs4-python/blob/master/1.3-bags-queues-and-stacks/6StacksImplementQueue-1.3.49.md 【 在 gungnir 的大作中提到: 】 : 你是不是被国内的算法书荼毒了……解决复杂问题不都是从特殊到一般，逐步建立完善模型的么…… : 为什么不会出现H比T先空的情况，人家原文后面给证明了，感觉你没仔细看……

【 在 lance6716 的大作中提到: 】 : 原始论文思路清晰，相比之下依次解释6个栈的作用还解释的不完备的这篇博客真是囫囵吞枣，而且还使用了要求的栈操作更底层的操作（所谓的浅拷贝） : 我自己写了一篇解释 https://github.com/lance6716/algs4-python/blob/master/1.3-bags-queues-and-stacks/6StacksImplementQueue-1.3.49.md : 你是不是自我感觉太良好了。自己没仔细看，没好好理解别人的文章还说别人囫囵吞枣。人家给了你原论文，给了有条理的解释，结尾还附上了Stack Overflow的讨论和进一步优化的可能。你没好好看就算了，你自以为理解了又开始鄙视人家写得不咋地。殊不知没有人家的整理和分享你自己能搞定这道题么。恕我直言就你这个心态压根就不是学算法的料。

? \_(ツ)_/?可是没有达到题目要求，用了栈api以外的操作你都没有发现吗。你怕是连原始论文都没看，不知道作者这6个栈的解释思路是他自己独创的。太自我感觉良好的是你吧 【 在 gungnir 的大作中提到: 】 : 你是不是自我感觉太良好了。自己没仔细看，没好好理解别人的文章还说别人囫囵吞枣。人家给了你原论文，给了有条理的解释，结尾还附上了Stack Overflow的讨论和进一步优化的可能。你没好好看就算了，你自以为理解了又开始鄙视人家写得不咋地。殊不知没有人家的整理和分享你自己能搞定这道题么。恕我直言就你这个心态压根就不是学算法的料。