将一个 stack/queue 移动到另一个 stack/queue 的 space 复杂度是多少？
What is the space complexity of moving one stack/queue to another stack/queue?
我正在尝试了解 space 将元素从一个堆栈移动到另一个堆栈的复杂性。
我在 leetcode 上找到了 this article，但有些出入。
假设我们通过执行三次 pop() 和 push() 将 stack1 (1-2-3) 移动到另一个 stack2，我们是否认为 O(1) 额外 space 因为我们删除了一个来自 stack1 的元素并在 stack2 中创建一个元素，因此没有使用 extra space？或者我们认为它是 O(n) space 复杂度，因为我们创建了一个与 stack1 大小相同的 stack2（但 stack1 不见了..）？
提前致谢！
这取决于您的堆栈是如何实现的。即什么是backing store？
如果堆栈实现为数组，则堆栈将初始化为一些默认容量，当前计数为 0。类似于：
s = int[10];
count = 0;
当您将某些东西压入堆栈时，该项目会被添加并且 count 会递增到 1。如果您尝试压入的项目超过数组所能容纳的数量，则会扩展数组。 （实际上，可能分配了一个新数组并将现有内容复制到其中。）
弹出东西时，count减1，返回s[count]。但是数组分配没有改变。
因此，如果堆栈实现为数组，那么从一个堆栈复制到另一个堆栈将需要额外的 O(n) space。至少是暂时的。
如果栈实现为链表：
头 > 节点 > 节点 > 节点 ...
那么一般pop就是returnshead，新的头就是head之前指向的节点。在这种情况下，堆栈占用的内存会随着每次弹出而减少。当然，添加到新堆栈会增加相同数量的内存分配。所以如果栈实现为链表，那么从一个栈复制到另一个栈是额外的O(1) space.
我正在尝试了解 space 将元素从一个堆栈移动到另一个堆栈的复杂性。
我在 leetcode 上找到了 this article，但有些出入。
假设我们通过执行三次 pop() 和 push() 将 stack1 (1-2-3) 移动到另一个 stack2，我们是否认为 O(1) 额外 space 因为我们删除了一个来自 stack1 的元素并在 stack2 中创建一个元素，因此没有使用 extra space？或者我们认为它是 O(n) space 复杂度，因为我们创建了一个与 stack1 大小相同的 stack2（但 stack1 不见了..）？
提前致谢！
这取决于您的堆栈是如何实现的。即什么是backing store？
如果堆栈实现为数组，则堆栈将初始化为一些默认容量，当前计数为 0。类似于：
s = int[10];
count = 0;
当您将某些东西压入堆栈时，该项目会被添加并且 count 会递增到 1。如果您尝试压入的项目超过数组所能容纳的数量，则会扩展数组。 （实际上，可能分配了一个新数组并将现有内容复制到其中。）
弹出东西时，count减1，返回s[count]。但是数组分配没有改变。
因此，如果堆栈实现为数组，那么从一个堆栈复制到另一个堆栈将需要额外的 O(n) space。至少是暂时的。
如果栈实现为链表：
头 > 节点 > 节点 > 节点 ...
那么一般pop就是returnshead，新的头就是head之前指向的节点。在这种情况下，堆栈占用的内存会随着每次弹出而减少。当然，添加到新堆栈会增加相同数量的内存分配。所以如果栈实现为链表，那么从一个栈复制到另一个栈是额外的O(1) space.