Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

How to Reverse a Stack Using Recursion
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings
The fast well prepared banner

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 1\n";


    // 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

  1. How to sort the given stack using recursion?
  2. How to sort the given stack using a temporary stack?
  3. Convert Infix to Postfix using different Precedence Values for In-Stack and Out-Stack
  4. How to reverse a number using a stack?
  5. 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 

 

 


Last updated on: 
October 27, 2023
Author

Abhinav Rawat

Product Manager @ Interview Kickstart | Ex-upGrad | BITS Pilani. Working with hiring managers from top companies like Meta, Apple, Google, Amazon etc to build structured interview process BootCamps across domains

Attend our Free Webinar on How to Nail Your Next Technical Interview

subscription-image
Thank you! Your subscription has been successfully submitted!
Oops! Something went wrong while submitting the form.

How to Reverse a Stack Using Recursion

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar