How to reverse a stack using recursion

To learn more about the Stack data structure, refer to this link.

A simple way to do this is to make a new stack and pop an element from the original stack. The popped element is pushed into the new stack, and this process is repeated until the original stack becomes empty.

However, we must make a recursive solution if we need to reverse the given stack. For this, it is helpful first to recall how recursion works.

Recursive Solution

Instead of storing the popped element in a separate, explicitly defined, and created stack, we can create a variable temp to store it. A recursive solution allows separate copies of this variable to be stored. They will be stored in separate stack frames on the recursive call stack for each call of the function (the recursive call stack doesn't need to be created by us explicitly in our code, the function itself creates it).

This is illustrated below:

When the recursive calls start tracking back once the base case (stack is empty) is reached, the value of temp in the function calls will be popped off the call stack. We note that inserting each temp value at the bottom of our original stack during the backtracking will eventually result in a reverse stack. However, since a stack is a FIFOFirst In, First Out. structure, we can only insert (push) elements at the top of the stack, so we need to develop a way to implement a functionality in which elements can be pushed to the bottom of the stack as well.

We can implement another recursive function, insertAtBottom(), which will be called inside the original function reverseStack(). When it is time to insert temp at the bottom of our stack during the backtracking of reverseStack(), we can first make a call to insertAtBottom().

The visual demonstration of our solution at work is shown below:

#include <iostream>
using namespace std;
class Stack
{
  int* stack_arr ;
  int max_size ;
  int current_size ;
  public:
    Stack(int max_cap)
    {
      stack_arr = new int[max_cap] ;
      max_size = max_cap ;
      current_size = 0 ;
    }
    bool isEmpty()
    {
      if(current_size == 0)
      {
        return 1 ;
      }
      else
      {
        return 0 ;
      }
    }
    void push(int element_to_push)
    {
      stack_arr[current_size] = element_to_push ;
      current_size++ ;
    }
    int pop()
    {
      int popped = stack_arr[current_size-1];
      current_size-- ;
      return popped;
    }
    void printStack()
    {
      for(int i = current_size-1 ; i >= 0 ; i--)
      {
        cout << stack_arr[i] << endl ;
      }
      cout << endl ;
    }
    
    int insertAtBottom(int temp) // the second recursive function
    {
      if(isEmpty()) 
      {
        push(temp); 
      }
      else 
      {
        int temp2 = pop();
        insertAtBottom(temp);
        push(temp2); // push temp2 back on original stack during backtracking
      }
    }
    
    void reverseStack() // the first recursive function
    {
      if(!isEmpty()) 
      {
        int temp = pop();
        reverseStack();
        insertAtBottom(temp); // insert temp at the bototm of the stack
      }
    }
};
int main() 
{
  int stack_size = 5 ;
  Stack example(stack_size);
  example.push(5);
  example.push(4);
  example.push(3);
  example.push(2);
  example.push(1);
  cout << "Original Stack:" << endl ;
  example.printStack();
  example.reverseStack();
  cout << "reversed Stack:" << endl ;
  example.printStack();
  return 0;
}

Explanation

The highlighted lines of code implement the two functions discussed, while the rest of the code is in the class definition of our stack and its main operations. These highlighted lines are explained below:

Lines 52–64: We implement the insertAtBottom() function in the following steps:
1. Pop an element from the original stack and store it in temp2.
2. Once our original stack has been emptied, push temp onto it.
3. During backtracking of this recursive function, push each temp2 back onto our original stack.
Lines 66–74: We implement the reverseStack() function in the following steps:
1. Pop an element from the original stack and store it in a variable temp.
2. Recursively do the same for the rest of the stack until it becomes empty. This way, the stack frame of each recursive call will contain a different value of temp.
3. During backtracking, push each temp back onto the original stack.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to reverse a stack using recursion

Recursive Solution

Code

Explanation