Given a stack S=<0, 1, 2, ..., 8, 9>, where 9 is the topmost element. The reversed stack S' is <9, 8, ..., 2, 1, 0>. The basic idea is to reverse the smaller stack subS=<0, 1, 2, ..., 8> first to get subS'=<8, ..., 2, 1, 0>, and then put 9 at the bottom of subS' to get S'. So:
void reverse_stack(stack<int> &s){ if(!s.empty()){ int ele = s.top(); s.pop(); reverse_stack(s); put_bottom(s, ele); } } But how to put an element at the bottom of a stack? we still can use recursion! void put_bottom(stack<int> &s, int ele){ if(s.empty()){ s.push(ele); return; } int topEle=s.top(); s.pop(); put_bottom(s, ele); s.push(topEle); }