Basic solution which comes in mind is to pop all element and sort and push into Stack again.

but as we don’t have extra space or Data Structure to sort stack.

We need to use inplace sorting, and to do so we need to have all elements out of stack.

One way to do so is to use “Recursion” .

It will use internally memory stack to store recursion values. but we can implement without initializing extra stack or memory.

Logic :

1) Recursively call function and pop all data.

2) Once stack is empty, Push last data.

3) While pushing data into stack pop top data and check for **order.**

4) Recursively call Sort function again and Push data finally.

Code :

#include <iostream>

#include <stack>

using namespace std;

void StackSort(int nTop, stack<int>& S);

//Step1

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)

{

//Step2

if(S.size() == 0)

{

S.push(nTop);

return;

}

//Step3

int nT = S.top();

if(nT > nTop)

{

int i = nTop;

nTop = nT;

nT = i;

}

//Step4

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;

}

If you want to share such question , solution or your experience of any company, Please do share at admin@gohired.in , As sharing is caring

http://ideone.com/cUS2sO