#include <iostream>

 #include <stack>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 void StackSort(stack<int>& s)

 {

     stack<int> tmp;

     while(!s.empty()){

         tmp.push(s.top());

         s.pop();

     }

     while(!tmp.empty()){

         if(s.empty()){s.push(tmp.top());tmp.pop();}

         else{

             int x=tmp.top();

             tmp.pop();

             if(x<=s.top())   s.push(x);

             else{

                 while(!s.empty()&&x>s.top()){

                     tmp.push(s.top());

                     s.pop();

                 }

                 s.push(x);

             }

         }

     }

 }

 void display(stack<int> s)

 { while (!s.empty()) cout<<s.top()<<endl,s.pop();

   cout<<endl;

 }

 int main(int argc,char**argv)

 { const int n{};

   srand((unsigned)time());

   stack<int> s;

   for (int i{};i<n;i++) s.push(rand()%);

   cout<<"Before sorting:"<<endl<<endl;  display(s);

   cout<<"After sorting:"<<endl; StackSort(s); display(s);

   return ;

 }