Write a program to sort a stack in ascending order  You should not make any assumptions about how the stack is implemented   The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

This is a question from "Cracking the Coding Interview". The solution given there uses a stack and follows "insertion sort" technique. I present the solution in "selection sort" technique and use recursion. I used C++.

Here is the code:

#include<iostream>

#include<stack>

#include<vector>

using namespace std;

template <typename X,typename Y>

int get_size(stack<X,Y>& st)

{

if(st.empty())

return 0;

else

{

X a = st.top();

st.pop();

int sz = 1 + get_size(st);

st.push(a);

return sz;

}

}

template <typename X,typename Y>

void stack_sort_private(stack<X,Y>& st,int size,int max,int now)

{

if(now == size)

{

st.push(max);

}

else

{

X a = st.top();

st.pop();

if(max<a)

std::swap(max,a);

stack_sort_private(st,size,max,now+1);

st.push(a);

}

}

template <typename X,typename Y>

void stack_sort(stack<X,Y>& st)

{

int size = get_size(st);

for(int i = size;i>0;--i)

{

X max = st.top();

st.pop();

stack_sort_private(st,i,max,1);

}

}

int main()

{

int array[] = {7,8,9,10,1};

vector<int> v(array,array + sizeof(array)/sizeof(int));

stack<int,vector<int> > st(v);

stack_sort(st);

while(!st.empty())

{

cout<<st.top()<<",";

st.pop();

}

return 0;

}