Last Updated: 16 Aug, 2020
Reverse Stack Using Recursion
Easy
Asked in companies
Reverse a given stack of 'N' integers using recursion. You are required to make changes in the input parameter itself.
Note: You are not allowed to use any extra space other than the internal stack space used due to recursion.
Example:
Input: [1,2,3,4,5]
Output: [5,4,3,2,1]
Input Format :
The first line of input contains an integer value 'N', denoting the size of the input Stack.
The second line contains 'N' single space-separated integers, denoting the stack elements, where the leftmost integer denotes the TOP element of Stack.
Output Format :
'N' single space-separated integers in a single line, where the leftmost integer denotes the TOP element of the reversed stack.
Approaches
We will be using two recursive methods:
- To Reverse the Stack: We will use recursion to iterate through the stack. For each top element, we will pop it and use recursion to reverse the remaining stack. After getting the stack reversed by recursion we can simply push the popped element to the bottom of the stack. The procedure to push the element at the bottom of stack is explained in following paragraph.
- To Push an element to the Bottom of Stack: For this, we will be using recursion. Now to push a given element to the bottom of the stack, we will iterate through the stack recursively. For each top element, we will pop it and call recursion to insert a given element at the bottom of the remaining stack. After recursive function does its work and adds the given element to the bottom of stack, then we can simply push the popped element to the top of the stack.
Algorithm:
- ReverseStack(stack)
- If the stack is empty, then return
- Pop the top element from the stack as top
- Reverse the remaining elements in the stack, call reverseStack(stack) method
- Insert the top element to the bottom of the stack, call InsertAtBottom(stack, top) method
- InsertAtBottom(stack, ele)
- If the stack is empty, push ele to stack, return
- Pop the top element from the stack as top
- Insert the ele to the bottom of the stack, call InsertAtBottom(stack, ele) method
- Push top to the stack.
Similar problems