提问者:小点点

在O(1)空间复杂度中反转队列


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

这里的答案:我可以在不使用堆栈的情况下反转队列吗?说堆栈是可能的。但我不明白这个过程是如何O(1)空间复杂度的:

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

第2步:将Stack的Front值加入Queue,然后弹出Stack的每个元素

堆栈不会为队列中的每个元素使用O(n)空间复杂度吗?


共1个答案

匿名用户

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