问O(1)空间复杂度的反向队列
EN

Stack Overflow用户

提问于 2020-01-30 07:53:25

回答 1查看 376关注 0票数 0

如何在O(1)空间复杂度内反转队列？

这里的答案是：Can I reverse a queue without using stack?说使用堆栈是可能的。但我不明白这个过程是O(1)空间复杂度：

步骤1:将队列中的每个元素入队，然后将每个元素出队到堆栈中

步骤2:将堆栈的前值放入队列中，然后取出堆栈的每个元素

Stack不会对队列中的每个元素使用O(n)空间复杂度吗？

回答已采纳

发布于 2020-01-30 11:17:37

当您将一个元素添加到堆栈中时，将其从队列中移除。队列大小和堆栈大小的总和不会改变，因此使用的内存总量保持不变。这就是为什么它需要O(1)空间。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/59977286

复制

相似问题

问O(1)空间复杂度的反向队列EN