[数据结构与算法]逆序栈（递归?）

给你一个栈，请逆序这个栈；
不能申请额外的数据结构，只能使用递归求解；

题解：
这道题难点就在于无法申请额外数据结构，可以用两个递归函数实现；
第一个递归函数GetBottom()主要用途是将栈底的数据出栈，并返回该数据的值；
所以我们可以使用递归让栈内的数据依次出栈，直到最后一个数据出栈后栈为空返回该数据的值，递归开始往回走，让之前出栈的值再依次进栈。
第二个递归函数Reverse()就是将栈逆序了；
这就需要我们开始调用GetBottom()函数将栈底数据先出栈，然后依次出栈，直到栈为空，此时最后一个出栈的一定是栈顶数据，这时递归就要往回走，我们只需要将出栈的数据依次再压入栈中即可，此时先入栈的是最后一个出栈的栈顶，最后一个入栈的就是之前的栈底，这样就完成了逆序；

ps：这个递归代码是很难想到的，也是非常非常非常巧妙的，不知道我什么时候可以写出这样的代码的😭

代码如下：

int GetBottom(stack<int> S)
{
	int result=S.pop();
	if(S.empty())
	return result;
	int last=GetBottom(S);
	S.push(result);//除栈底数据外的数据再依次进栈 
	return last;
} 
void Reverse(stack<int> S)
{
	if(S.empty())
	return ;
	int i=GetBottom(S);
	Reverse(S);
	S.push(i); 
}