3

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

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

我想出了下面的代码，它正在工作，但是not convinced that it is O(1) space because i have declared "int temp" exactly n times，假设堆栈中最初有 n 个元素）so it has taken O(n) space.

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

代码：

#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();
}
4

2 回答 2

3

我能想到的唯一方法是使用链表编写自己的堆栈，然后交换头/尾指针和“方向”指示器，该指示器告诉您的例程在您推/弹出时前进或后退。我能想到的任何其他方式都是 O(n)。

如果您知道 n 的上限，您也可以使用数组/索引而不是列表。

这样做是否有意义可能取决于这样做的原因和语言。

于 2013-10-14T08:13:11.030 回答
3

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

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

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

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

总而言之，需要 O(n^2) 步骤，但我们只需 O(1) 空间即可管理。

于 2013-10-14T17:21:19.197 回答