2.6K
Question: You are given a stack and you have to reverse it, using only stack operations push and pop.
The algorithm for the above problem can be given in this way:-
- First POP all elements of the stack till it becomes empty
- Now for each upward step in the recursion, push the elements at the bottom of the stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | void reverseStack( struct stackNode * top) { int data; if (isStackEmpty(top)) return ; //get the top data data = POP(top); //recursive call for the next top element reverseStack(top); //after the recursion ends, we need to insert the numbers at the Bottom insertAtBottom(top, data); } void insertAtBottom( struct stackNode * top, int data) { int temp; //check for terminating condition of recursive call if (isStackEmpty(top)) { //when the stack is empty, just add the data //this will be the last data of original stack top = push(top,data); return ; } //again we get the top elements one by one temp = POP(top); //a recursive call insertAtBottom(top, data); top = push(top, temp); } |