Reverse Stack Using Recursion

Easy
0/40
Average time to solve is 21m
profile
Contributed by
364 upvotes
Asked in companies
AmazonOracleRazorpay

Problem statement

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]

add image

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3
2 1 3
Sample Output 1 :
3 1 2
Explanation to Sample Input 1 :
Reverse of a give stack is 3 1 2 where first element becomes last and last becomes first.                   
Sample Input 2 :
2
3 2
Sample Output 2 :
2 3
Constraints :
0 <= N <= 10^3
Where 'N' is the number of elements in the given stack.

Time Limit: 1 sec
Hint

Use the recursion call stack to store the elements of the stack and reverse it.

Approaches (1)
Recursive Approach

We will be using two recursive methods:

  1. 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.
  2. 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: 

  1. ReverseStack(stack)
    1. If the stack is empty, then return
    2. Pop the top element from the stack as top
    3. Reverse the remaining elements in the stack, call reverseStack(stack) method
    4. Insert the top element to the bottom of the stack, call InsertAtBottom(stack, top) method
  2. InsertAtBottom(stack, ele)
    1. If the stack is empty, push ele to stack, return
    2. Pop the top element from the stack as top
    3. Insert the ele to the bottom of the stack, call InsertAtBottom(stack, ele) method
    4. Push top to the stack.
Time Complexity

O(N^2), where ‘N’ is the total number of elements in the given stack.

 

In the worst case, reverseStack method will be called for each element in the stack( requires O(N)) time, and for each call of the reverse stack, we call InsertAtBottom which also takes O(N) time.

Space Complexity

O(N), where ‘N’ is the total number of elements in the given stack.

 

In the worst case, the depth of recursion can extend up to O(N). So, extra space will be required for the recursion stack.

Code Solution
(100% EXP penalty)
Reverse Stack Using Recursion
Full screen
Console