How to Reverse a Stack Using Recursion

The stack data structure is a big part of coding interviews at tech companies. This article will discuss one crucial previously asked FAANG problem on stacks.

• Problem Description With Example
• Approach to Solve the Problem
• Code to Reverse a Stack Using Recursion
• Complexity Analysis: Reverse a Stack Using Recursion
• FAANG Interview Questions on Reversing a Stack Using Recursion
• FAQs on Reversing a Stack Using Recursion

Problem Description With Example

Given: A stack of integers.

Task: Reverse the stack using recursion.

Constraints: We are not allowed to use any loop constructs like for, while, or do-while.

Example:

Input Stack: 

Reversed Stack:

Here the initial stack was [1,2,3,4,5] and after reversing, it becomes [5,4,3,2,1].

Approach to Solve the Problem

The problem name itself declares the solution should be recursive.

The stack data structure has two methods: push and pop on the top of the stack. If we have to reverse the stack, we have to pop all elements from the original stack and push them in reverse order in some other stack. In this way, we get the new reversed stack.

However, it’s possible to do it without using extra stack objects, using recursion. A recursive function behaves like a stack. In this method, we will create the recursive function, pop all items from our stack, and store those popped items in the function call stack.

After popping all the items, the stack will become empty. Then, we will start pushing the new item, which the call stack of recursion contains. Finally, we will push them to the bottom of our empty stack.

In short, what we do is:

1. Use recursion for popping the top element of the given stack and storing it in the recursion stack, and repeat this until the stack is not empty.
2. While turning back to the previous state of recursion, push the stored element in the recursion stack at the bottom of the given input stack.

Visualization using an example:

Solution Steps:

1. Create a recursive function called rec to reverse the input stack.
2. In recursion, pop the top element of the stack and hold it in the recursive function call stack until the input stack is empty.
3. While going back in the recursion, push the held element in the recursion call stack at the bottom of the input stack.

Code to Reverse a Stack Using Recursion

Code:

#include <bits/stdc++.h>

using namespace std;

// Recursive function

// which inserts an element

// at the bottom of a stack.

void insert(int tp, stack<int> &st)

{

    if (!st.empty())

    {

        /*

         Here, the Function Call Stack holds all items until our stack is not empty.

         When the stack becomes empty, we insert items in the stack; now, we will insert the items in the reverse order.

       */

        int a = st.top();

        st.pop();

        insert(tp, st);

        st.push(a);

    }

    else

        st.push(tp);

}

// Function that

// reverses the input stack

void recursiveReverse(stack<int> &st)

{

    if (!st.empty())

    {

        // Here we hold all items in Function

        // Call Stack until stack is not empty.

        int tp = st.top();

        st.pop();

        recursiveReverse(st);

        // Here, we push all the items that are on hold

        // in Function Call Stack

        // one by one. Every item is

        // inserted at the bottom of the input stack.

        insert(tp, st);

    }

}

int main()

{

    // Creating stack objects.

    stack<int> st;

    // Pushing elements in the stack.

    st.push(1);

    st.push(2);

    st.push(3);

    st.push(4);

    st.push(5);

    // Initial order of stack elements according to items placed.

    cout << “Stack Initial: “

         << “5 4 3 2 1n”;

    // Calling a recursive function to reverse the stack.

    recursiveReverse(st);

    cout << “Stack Final: “;

    // Popping elements one by one from stack and printing it.

    while (st.size())

    {

        int tp = st.top();

        cout << tp << ” “;

        st.pop();

    }

}

Output:

Stack Initial: 5 4 3 2 1

Stack Final: 1 2 3 4 5

Complexity Analysis: Reverse a Stack Using Recursion

Let us now discuss the time and space complexity of reversing a stack using recursion.

Time Complexity: O(n2).

For each element on top of the stack, we’re popping the whole stack out, and then we’re placing that top element at the bottom, which uses O(n) operations. Moreover, we need to do these O(n) operations for every element in the input stack. Hence, there will be n2 operations that give the time complexity of O(n2).

Space Complexity: O(n)

We are using a recursion call stack to store the items in the input stack temporarily. In the worst case, there will be n items stored in the recursive call stack, making the space complexity O(n).

FAANG Interview Questions on Reversing a Stack Using Recursion

• How to sort the given stack using recursion?
• How to sort the given stack using a temporary stack?
• Convert Infix to Postfix using different Precedence Values for In-Stack and Out-Stack
• How to reverse a number using a stack?
• How to reverse a stack without using extra space in linear time?

Visit the Interview Questions page for more sample interview questions asked at FAANG and other tier-1 tech companies.

FAQs on Reversing a Stack Using Recursion

Question 1: How to prove the time complexity of reversing a stack using recursion and recurrence relations? 

Say there are n elements in the stack, according to our algorithm we are calling recursion and popping elements in it. in each recursive call we are popping one element. So, the recurrence relation will be:

T(n) = T(n-1) + n after popping one item

        = T(n-2) + (n-1) + n after popping two items

        = T(n-3) + (n-2) + (n-1) + n after popping three items

And so on, until we pop all the items in the stack.

The final relationship will be:

T(n) = T(n-(n-1)) + T(n-(n-2)) + … + (n-2) + (n-1) + n

        = T(1) + T(2) + … + (n-2) + (n-1) + n

        = 1 + 2 + … + (n-2) + (n-1) + n

        = n × (n+1)/2

It gives the quadratic result; hence the complexity of reversing the stack using recursion will be O(n2).

Question 2: How are we inserting the top element at the bottom of the stack? 

Let’s call the given stack an input stack. Now, we pass our input stack in the recursive function. According to the algorithm, in the recursive function, we pop the elements from the input stack and store them in the recursive call stack until the input stack becomes empty. After the input stack becomes empty, we push the top element, which the recursive stack in the input stack contains. Then, while returning down the recursion tree, we push all the elements stored in the recursive call stack one by one into the input stack.

Are You Ready to Nail Your Next Coding Interview?

Whether you’re a Coding Engineer gunning for Software Developer or Software Engineer roles, or you’re targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of Software Engineers to crack the most challenging coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

————

Article contributed by Omkar Deshkmukh