#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;
}