递归反转一个栈 有代码 请解释程序解决方案

递归反转一个栈 有代码 请解释程序
目标:递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度o(1)
博主说: 算法思想：汉诺塔的思想，非常复杂，玩过九连环的人都想得通的

C/C++ code

static void ReverseStack(ref Stack stack){    if (stack.Count == 0)        return;    object top = stack.Pop();    ReverseStack(ref stack);    if (stack.Count == 0)    {        stack.Push(top);        return;    }    object top2 = stack.Pop();    ReverseStack(ref stack);//p1    stack.Push(top);    ReverseStack(ref stack);//p2    stack.Push(top2);        }

请问两个问题:
第一个: 注释p1,p2两处的递归用来干什么?顺序可以点到吗?
第二个:如果做到只用一个堆栈就搞定反转的?



[解决办法]

探讨

递归本身就很占 空间了，隐形的？哈哈。

[解决办法]
我貌似看懂了
例如栈
1
2 object top = stack.Pop();后栈变为 2
3 3
4 4
ReverseStack(ref stack); 后站变为
4
3
2
object top2 = stack.Pop();后变为
3
2
（可以注意到1是栈顶元素，4是栈底元素）
然后 ReverseStack(ref stack);//p1 变为
2
3
然后 stack.Push(top);变为
1
2
3
（注意到到这一步你可以发现他把栈底元素4取出来了，我感觉这是理解这个算法的关键）
最后几步就很简单了，
3
2
1
最后到
4
3
2
1

查看更多 下一篇