|
This post is completed by 2 users
|
Add to List |
392. Reverse a Stack using recursion - In Place (Without using extra memory)
Objective: Given a Stack, write an algorithm to reverse the stack.
Example:
Original Stack: [14, 9, 67, 91, 101, 25] Reversed Stack: [25, 101, 91, 67, 9, 14]
Approach: Use Recursion
In this solution, we need two recursive functions. reverse() and insert_at_bottom().
reverse() - this function will be called by the driver. In this function, Pop the element from the stack make a recursive call to reverse() till the stack is not empty. This will put all the popped elements in the function stack, and our stack will be empty, in tail recursion insert all these popped elements at the bottom of the stack, one after another using insert_at_bottom().
insert_at_bottom() - This function is called with element passed as a parameter and objective of this function to insert the element at the bottom of the stack. If stack is empty, just push the element and if stack is not empty then pop the top element and make a recursive call to insert_at_bottom(), this will pop out all the elements to the function stack and our stack will be empty so that element (passed as parameter) will be pushed to the empty stack and after that all the earlier popped element will be pushed back on top of that.
Walk Through:
Given Stack: [1, 2, 3, 4]
Let's first see what happens inside the reverse() function
As you can see the insert_at_bottom() is called 4 times, once for each element. insert_at_bottom() itself is a recursive function. Let's see what is happening inside the function for one instance. insert_at_bottom(4) is the last time this function was called and produced our final result as well. let's take a look inside.
Output:
Original Stack: [14, 9, 67, 91, 101, 25] Reversed Stack: [25, 101, 91, 67, 9, 14]