algorithm - 其中的递归和内存使用

Question

我最近看到一个问题需要。在 O(1) 空间中反转堆栈。

1) 堆栈不一定是数组...我们无法访问索引。
2)元素数量未知。

我想出了下面的代码，它可以工作，但不相信它是 O(1) 空间，因为我已经声明了 n 次“int temp”，假设最初有 n 个元素stack)所以它占用了 O(n) 的空间。

请告诉我是否正确，是否有更好的方法来找到解决方案？

代码:

#include<bits/stdc++.h>
using namespace std;
stack<int>st;
void rec()
{
    if(st.empty()) 
        return;
    int temp=st.top();
    st.pop();

    rec();
    st.push(temp);
}
int main()
{
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);

    rec();
}

Answer 1

您可以在一个包含 n 个元素的数组中“背靠背” 构建 2 个堆栈。基本上堆栈 #1 是一个“正常”堆栈，堆栈 #2 从数组末尾“向下”增长。

只要 2 个堆栈一起包含所有 n 个元素，它们之间就没有间隙，因此例如在这种情况下从堆栈 #1 弹出一个元素并立即将其插入堆栈 #2 甚至可以在不移动任何数据的情况下完成:只需将堆栈 #1 的 top 指针向下移动，并将堆栈 #2 的 top 指针物理上向下移动(但逻辑上 向上)。

假设我们从堆栈 #1 中的所有元素开始。现在你可以弹出除了最后一个之外的所有，立即将每个插入堆栈#2。您可以弹出并存储在临时位置 x 的最后一个元素(O(1) 额外存储空间，这是我们允许的)。现在弹出堆栈 #2 中的所有 n-1 个项目，依次将每个项目推回堆栈 #1，然后最后将 x 推回(现在为空)堆栈 #2。此时，我们已经成功地删除了堆栈 #1 中的底部元素，并将其放在堆栈 #2 的顶部(好吧，它是唯一的元素)。

现在只是递归:假设我们只有 n-1 项，然后解决这个较小的问题。继续递归，直到所有元素都以相反的顺序被压入堆栈#2。在最后一步中，弹出它们中的每一个并将它们推回堆栈 #1。

总而言之，需要 O(n^2) 个步骤，但我们只用了 O(1) 个空间。