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.
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);
}