Reverse a Stack Using Recursion

Difficulty: Easy

Asked in: Yahoo, Amazon, Adobe

Understanding The Problem

Problem Description

Given a stack of integers st, write a program to reverse the stack using recursion.

Problem Note

• You are not allowed to use loop constructs like while, for, etc, Return st after reversing it using recursion. It is mandatory to reverse st using recursion.

Example 1

Input: st = [1, 5, 3, 2, 4]
Output:[4, 2, 3, 5, 1]
Explanation: After reversing the stack [1, 5, 3, 2, 4] becomes [4, 2, 3, 5, 1].

Example 2

Input: st = [5, 17, 100, 11]
Output: [11, 100, 17, 5]
Explanation: After reversing the stack [5, 17, 100, 11] becomes [11, 100, 17, 5]

Solution

The problem name itself addresses the solution to be a recursive solution. To understand what is a recursive solution, please refer here.

You must have known that a stack usually comprises two operations, i.e. push and pop operations on the top of the stack. So, If we have to reverse a stack, then we have to pop the elements of the stack and push it to another auxiliary stack one by one. In this way, the auxiliary stack will be the same stack in reverse order.

But we are not looking to use an auxiliary stack, but we can use recursion. And a recursive function behaves like a stack. So, What we are going to do that is we can create a recursive function and pop all stack items and stores the popped item in the function call stack. And when the input stack becomes empty, we push the new item stored in the call stack at the bottom of the input stack.

You can practice this problem here.

In short, we will take out the top element of the input stack and store it in the recursion stack until the stack becomes empty and while returning to the previous state of recursion, we push the stored element in each recursion stack at the bottom of the input stack.

Look at the below example:

Solution Steps

• Create a recursive function recur to reverse the stack.
• Pop the top element in each stack of recursion and hold the element in function call Stack until we reach the end of the stack
• While moving back in the recursion tree, push the held element of each recursion call stack at the bottom of the stack.

Pseudo Code

int insert_at_bottom(int x, stack st) {
    if(st is empty) {
        st.push(x)
    }
    else {
        int a = st.top()
        st.pop()
        insert_at_bottom(x)
        st.push(a)
    }
}
void reverse(stack st) {
    if(st is not empty) {
        int st = st.top()
        st.pop()
        reverse(st)
        insert_at_bottom(x, st)
    }
}
// driver function
int[] reverseStack(int[] st) {
    reverse(st)
    return st
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n)

Critical Ideas To Think

• Why is the time complexity is O(n²)? Answer: For each element on top of the stack we are popping the whole stack out placing that top element at the bottom which takes O(n) operations. And this O(n) operations are performed for every value of the stack leaving a quadratic time complexity.
• How we are inserting the top element at the bottom of the stack? Answer: We pop each top element of the stack and store it in the call stack frame until the stack becomes empty. As soon as the stack becomes empty, we put the top element on the empty stack and then we push all the elements stored in the call stack frame while returning down the recursion tree.
• Take an example yourself and follow the above steps to test how the solution is working.
• Can you reverse a stack without recursion in linear time complexity? If yes, then what data structure will you use for the solution?

Suggested Problems To Solve

• Sort a stack using recursion
• Reverse a Doubly linked list using recursion
• Sort a stack using a temporary stack
• Infix to Postfix using different Precedence Values for In-Stack and Out-Stack
• Reverse a number using stack
• Reverse a stack without using extra space in linear time.

Please comment down below if you have a better insight in the above approach.

Happy Coding, Enjoy Algorithms!