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里面只有一個元素（此時是遞歸到底部，應(yīng)該結(jié)束了）琼牧，就返回恢筝，否則就不返回。具體實現(xiàn)是先pop出來一個巨坊，判斷剩下的是不是空棧撬槽。
int a = s.top();
s.pop();
if(s.empty())
{
s.push(a);
return ;
}
else
{
s.push(a);
}
}
//真正的遞歸思想，就是不需要考慮遞歸的中間過程趾撵，只需要知道
// 1.上一層遞歸出來長成什么樣子
// 2.這一層遞歸如何利用上一層遞歸的結(jié)果
// 3.結(jié)束遞歸的條件
//這里的核心思想還是兩兩交換（即是頂和底交換侄柔，當然共啃，單個函數(shù)來看，不陷入遞歸的細節(jié)暂题，就是兩兩交換）
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;
}
