Question

如何用递归倒置一个栈？

Answer 1

如果递归函数只能在堆栈上传递元素，而不是通过堆栈本身传递指针，我们假定应用于函数参数+函数的空间之和不超过K元素。然后函数的每个调用相加为O（k，2）逆对的最大值，最终结果需要一个O（n - 2）逆对。所以最小复杂度是O（n？2）.

---

当然，有一点点的元素是可复制的证据。但我不认为复制是没有意义的，因为我们只考虑堆栈结尾处栈中元素的位置。

开始验证

我认为在堆栈上构建链表是可能的，其原理如下：堆栈为s＝{ 1, 2, 3，4, 5 }。然后每次递归，都可以弹出一个（顺序为54321），而每个递归结构都列出了头- > 5 - > 4 - > 3 - > 2 - > 1，然后S是空的，你可以直接从头部把所有的值推回来。

第二步

题目愿意是不要用递归堆栈空间作为程序使用的空间，否则没有解决方案，应该是很明显的吗？见“程序员选择100个问题（39）-反向线[数据结构]。巧妙的方法是使用递归堆栈空间从原始堆栈弹出中保存元素，并避免额外的O（n）数组。解的时间复杂度为o（n·2）。

最后一步

倒置堆栈：1。顶部= POP（）2。倒堆。将顶部插入堆栈的下部，如何将它插入堆栈的底部？这是另一种递归吗？

觉得这个问题大脑崩溃了，我的文化水平是不够的，答不出来，你要不要另请高明的好？

Answer 2

#include <cstdio>

#include <algorithm>

using namespace std;

const int MaxS = 100;

int stack[MaxS]; int head = 0;

void push(int x){
stack[head++] = x;
}

int pop(){
return stack[--head];
}

bool empty(){
return head == 0;
}

int cnt = 0;

void f1(){
int a[1];
if (empty())
return;
cnt++;
a[0] = pop();
f1();
return ;
}

void f2(){
int a[1];
if (!cnt)
return ;
cnt--;
push(a[0]);
f2();
return ;
}

int main(){
for (int i = 0; i < 10; i++)
push(i);
for (int i = 0; i < 10; i++)
printf("%d ", stack[i]);
puts("");
f1();
f2();
for (int i = 0; i < 10; i++)
printf("%d ", stack[i]);
}


g++ a.cpp -o a
if with O2, f2 will become:
_Z2f2v:
.LFB468:
.cfi_startproc
movl cnt(%rip), %edx
testl %edx, %edx
jne .L14
rep ret
.p2align 4,,10
.p2align 3
.L14:
movl head(%rip), %ecx
leal (%rcx,%rdx), %edi
movl %ecx, %eax
.L11:
movslq %eax, %rsi
addl $1, %eax
cmpl %edi, %eax
movl $0, stack(,%rsi,4)
jne .L11
leal (%rdx,%rcx), %eax
movl $0, cnt(%rip)
movl %eax, head(%rip)
ret
.cfi_endproc