Reverse a stack using recursion

Here, we are going to reverse a stack using recursion. We are not supposed to use any loop constructs like for loop, while loop, do-while loop, etc. We should use the recursion method to reverse a stack.

For example: input: s = [10, 20, 30, 40, 50]

Output: [50, 40, 30, 20, 10]

Explanation: When the stack s is reversed then the output would be [50, 40, 30, 20, 10].

There are various ways to reverse a stack using recursion. The most common way of reversing a stack is to use an auxiliary stack. First, we will pop all the elements from the stack and push them into the auxiliary stack. Once all the elements are pushed into the auxiliary stack, then it contains the elements in the reverse order and we simply print them. But, here, we will not use the auxiliary stack. We will use a recursion method to reverse a stack where recursion means calling the function itself again and again.

In the recursion method, we first pop all the elements from the input stack and push all the popped items into the function call stack until the stack becomes empty. When the stack becomes empty, all the items will be pushed at the stack. Let’s understand this scenario through an example.

For example:

Input stack: 1, 2, 3, 4, 5

Output: 5, 4, 3, 2, 1

Solution: Firstly, all the elements from the input stack are pushed into the function call stack

Step 1: Element 5 is pushed at the bottom of the stack shown as below:

Step 2: Element 4 is pushed at the bottom of the stack shown as below:

Step 3: Element 3 is pushed at the bottom of the stack shown as below:

Step 4: Element 2 is pushed at the bottom of the stack shown as below:

Step 5: Element 1 is pushed at the bottom of the stack shown as below:

Implementation in C

  #include <stdio.h>   #define MAXSIZE 10  #define TRUE 1  #define FALSE 0   // Defining the structure of stack type   struct Stack {      int top;      int array[MAXSIZE];  } st;    // initialization of top variable   void initialize() {   st.top = -1;  }  // checking whether the stack is full or not   int isFull() {         if(st.top >= MAXSIZE-1)          return TRUE;      else          return FALSE;  }   // checking whether the stack is empty or not  int isEmpty() {   if(st.top == -1)       return TRUE;   else       return FALSE;  }     // function to push the element into the stack.  void push(int num) {      if (isFull())          printf(“Stack is Full…n”);      else {          st.array[st.top + 1] = num;          st.top++;      }  }     // function to pop the element from the stack  int pop() {      if (isEmpty())          printf(“Stack is Empty…n”);      else {       st.top = st.top – 1;          return st.array[st.top+1];      }  }     // function to print the elements of stack.  void printStack(){  // condition to check whether the stack is empty or not.   if(!isEmpty())  {       int temp = pop();       printStack();       printf(” %d “, temp);       push(temp);      }  }  // function to insert the element at the bottom of the stack.  void insertAtBottom(int item) {      if (isEmpty()) {          push(item);      } else {         int top = pop();          insertAtBottom(item);          push(top);      }  }   // function to reverse the order of the stack.  void reverse() {      if (!isEmpty()) {           int top = pop();          reverse();          insertAtBottom(top);      }  }    int getSize(){   return st.top+1;  }  // Definition of main() method   int main() {   initialize(st);    // calling initialize() method    push(1);     // calling push() method      push(2);   // calling push() method      push(3);    // calling push() method      push(4);    // calling push() method      push(5);    // calling push() method      printf(“Original Stackn”);      printStack();      reverse();      printf(“nReversed Stackn”);      printStack();  // calling printStack() method      return 0;  }  

Output

Next TopicDetect cycle in a directed graph

Reverse a stack using recursion

Reverse a stack using recursion

Implementation in C

Cycle Sort

Characteristics of OLAP

You may also like