algorithm - 不使用任何数据结构的反向堆栈

Question

如何在不使用任何(额外)数据结构的情况下反转堆栈？任何建议或伪代码都可能有所帮助。我尝试但找不到任何可行的解决方案。这里的问题是我也不知道堆栈的大小。如果我知道我至少可以继续创建一些东西，请提前致谢。

Answer 1

这可以通过双递归来完成，如follows: .

void insert_at_bottom(node **stack, int data)
{
     if( isempty(*stack) ){
          push(stack,data);
          return;
     }
     int temp=pop(stack);
     insert_at_bottom(stack,data);
     push(stack,temp);
}  


void rev_stack(node **stack)
{
     if( isempty(*stack) ) return;
     int temp = pop(stack);
     rev_stack(stack);
     insert_at_bottom(stack,temp);
}