include <iostream>
include <stack>
using namespace std;
void printInfo(stack<int> s)
{
int a ;
while(!s.empty())
{
a = s.top();
cout << a << " . " ;
s.pop();
}
cout << endl;
return ;
}
void reverseStack(stack<int> &s)
{
//如果接收到一个无效输入（空栈），返回
if(s.empty())
return ;
else
{
//如果s里面只有一个元素（此时是递归到底部，应该结束了），就返回，否则就不返回。具体实现是先pop出来一个，判断剩下的是不是空栈。
int a = s.top();
s.pop();
if(s.empty())
{
s.push(a);
return ;
}
else
{
s.push(a);
}
}
//真正的递归思想，就是不需要考虑递归的中间过程，只需要知道
// 1.上一层递归出来长成什么样子
// 2.这一层递归如何利用上一层递归的结果
// 3.结束递归的条件
//这里的核心思想还是两两交换（即是顶和底交换，当然，单个函数来看，不陷入递归的细节，就是两两交换）
int temp1 = s.top();
s.pop();
reverseStack(s);
int temp2 = s.top();
s.pop();
reverseStack(s);
s.push(temp1);
reverseStack(s);
s.push(temp2);
}
int main()
{
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
cout << "-------------before recursion------------" << endl;
printInfo(s);
cout << "-------------after recursion------------" << endl;
reverseStack(s);
printInfo(s);
return 0;
}
