stack - 将一个堆栈/队列移动到另一个堆栈/队列的空间复杂度是多少？

Question

我试图了解将元素从一个堆栈移动到另一个堆栈的空间复杂性。

我在 leetcode 上找到了这篇文章，但存在一些差异。

假设我们通过执行 pop() 和 push() 3 次将 stack1 (1-2-3) 移动到另一个 stack2，我们是否会考虑 O(1) 额外空间，因为我们从 stack1 中删除一个元素并在 stack2 中创建一个元素因此没有使用额外的空间？或者我们认为它是 O(n) 空间复杂度，因为我们创建了一个与 stack1 大小相同的 stack2（但 stack1 已经消失了..）？

提前致谢！

标签： stackqueuetime-complexitybig-ospace-complexity

Answer 1

这取决于您的堆栈是如何实现的。也就是说，什么是后备存储？

如果堆栈被实现为一个数组，那么堆栈将被初始化为一些默认容量，当前计数为 0。类似于：

s = int[10];
count = 0;

当您将某些内容压入堆栈时，会添加该项目并将其count递增到 1。如果您尝试压入的项目数量超过了数组将容纳的数量，则该数组将被扩展。（实际上，可能分配了一个新数组并将现有内容复制到其中。）

当你弹出一些东西时，count减 1，然后s[count]返回。但是数组分配没有改变。

因此，如果堆栈实现为数组，则从一个堆栈复制到另一个堆栈将需要 O(n) 额外空间。至少暂时。

如果栈实现为链表：

头>节点>节点>节点...

然后通常pop只返回head，新的头是head先前指向的节点。在这种情况下，堆栈占用的内存会随着每次弹出而减少。当然，添加到新堆栈会增加相同数量的内存分配。因此，如果堆栈实现为链表，则从一个堆栈复制到另一个堆栈是 O(1) 额外空间。