#include <iostream>
#include <stack>
using namespace std;
void StackSort(int nTop, stack<int>& S);
void StackSortUtil(stack<int>& S)
{
for(int i=0;i<S.size(); ++i)
{
int nTop = S.top();
S.pop();
StackSort(nTop, S);
}
}
void StackSort(int nTop, stack<int>& S)
{
if(S.size() == 0)
{
S.push(nTop);
return;
}
int nT = S.top();
if(nT > nTop)
{
//swap
int i = nTop;
nTop = nT;
nT = i;
}
S.pop();
StackSort(nT,S);
S.push(nTop);
}
int printStack(stack <int>& S){
while( ! S.empty()) {
cout<< S.top() <<"\n";
S.pop();
}
}
int main()
{
std::stack<int> Stk;
Stk.push(10);
Stk.push(13);
Stk.push(41);
Stk.push(72);
Stk.push(15);
StackSortUtil(Stk);
cout << "==Stack in decending order==\n";
printStack(Stk);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RhY2s+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIFN0YWNrU29ydChpbnQgblRvcCwgc3RhY2s8aW50PiYgUyk7Cgp2b2lkIFN0YWNrU29ydFV0aWwoc3RhY2s8aW50PiYgUykKewogICAgZm9yKGludCBpPTA7aTxTLnNpemUoKTsgKytpKQoJewoJCWludCBuVG9wID0gUy50b3AoKTsKCQlTLnBvcCgpOwoJCVN0YWNrU29ydChuVG9wLCBTKTsKCX0KfQoKdm9pZCBTdGFja1NvcnQoaW50IG5Ub3AsIHN0YWNrPGludD4mIFMpCnsKCWlmKFMuc2l6ZSgpID09IDApCgl7CgkJUy5wdXNoKG5Ub3ApOwoJCXJldHVybjsKCX0KCQoJaW50IG5UID0gUy50b3AoKTsKCglpZihuVCA+IG5Ub3ApCgl7CgkJLy9zd2FwCgkJaW50IGkgPSBuVG9wOwoJCW5Ub3AgPSBuVDsKCQluVCA9IGk7Cgl9CgoJUy5wb3AoKTsKCVN0YWNrU29ydChuVCxTKTsKCglTLnB1c2goblRvcCk7Cn0KaW50IHByaW50U3RhY2soc3RhY2sgPGludD4mIFMpewogICAgd2hpbGUoICEgUy5lbXB0eSgpKSB7CiAgICAgICAgY291dDw8IFMudG9wKCkgPDwiXG4iOwogICAgICAgIFMucG9wKCk7CiAgICB9Cn0KaW50IG1haW4oKQp7CglzdGQ6OnN0YWNrPGludD4gU3RrOwoJU3RrLnB1c2goMTApOwoJU3RrLnB1c2goMTMpOwoJU3RrLnB1c2goNDEpOwoJU3RrLnB1c2goNzIpOwoJU3RrLnB1c2goMTUpOwoKCVN0YWNrU29ydFV0aWwoU3RrKTsKICAgIGNvdXQgPDwgIj09U3RhY2sgaW4gZGVjZW5kaW5nIG9yZGVyPT1cbiI7CiAgICBwcmludFN0YWNrKFN0ayk7CgoJcmV0dXJuIDA7Cn0=