C Program to Reverse a Stack using Recursion

  • Write a program in C to reverse a stack using recursion.

Given a stack of integers, we have to reverse the stack elements using recursion. We cannot use any loop like for, while etc and we can only use push, pop, isEmpty and isFull functions of given stack. 

Input Stack
   2  <--- Top
   4
   8
   9
Output Stack 
   9 <--- Top
   8
   4
   2
Here we are going to use recursion to reverse the stack elements. We will store the top elements of stack on function stack one by one until stack becomes empty. When stack becomes empty, we will insert an element at the bottom of stack and then insert all the elements stores in function stack back in same sequence. Here we will use two user defined functions "insertAtBottom" and "reverse".
  • void insertAtBottom(int num) : This function inserts a number "num" at the bottom of stack using recursion.
  • void reverse() : This function pop's top element and store it in function stack. Then it recursively calls itself to reverse remaining stack. Once remaining stack elements are reversed, it calls insertAtBottom function to insert top element at the bottom of stack.
For Example

Output Stack
First 2 is inserted at the bottom of stack.
   2 <--- Top
Then 4 is inserted at the bottom of stack.
   2 <--- Top
   4
Then 8 is inserted at the bottom of stack.
   2 <--- Top
   4
   8
Then 9 is inserted at the bottom of stack.
   2 <--- Top
   4
   8
   9

C program to reverse a stack data structure using recursion

#include <stdio.h>

#define MAXSIZE 7
#define TRUE 1
#define FALSE 0 

// Structure defining Stack data structure
struct Stack {
    int top;
    int array[MAXSIZE];
} st;

/*
Initializes the top index to -1
*/
void initialize() {
 st.top = -1;
}

/*
 Checks if Stack is Full or not 
*/
int isFull() {   
    if(st.top >= MAXSIZE-1)
        return TRUE;
    else 
        return FALSE;
}

/*
 Checks if Stack is Empty or not
*/
int isEmpty() {
 if(st.top == -1)
     return TRUE;
 else 
     return FALSE;
}

/*
 Adds an element to stack and then increment top index 
*/
void push(int num) {
    if (isFull())
        printf("Stack is Full...\n");
    else {
        st.array[st.top + 1] = num;
        st.top++;
    }
}

/*
 Removes top element from stack and decrement top index
*/
int pop() {
    if (isEmpty())
        printf("Stack is Empty...\n");
    else {
     st.top = st.top - 1;
        return st.array[st.top+1];
    }
}

/*
 Prints elements of stack using recursion
*/
void printStack(){
 if(!isEmpty()){
     int temp = pop();
     printStack();
     printf(" %d ", temp);
     push( temp);
    }
}
void insertAtBottom(int item) {
    if (isEmpty()) {
        push(item);
    } else {
 
        /* Store the top most element of stack in top variable and 
        recursively call insertAtBottom for rest of the stack */
        int top = pop();
        insertAtBottom(item);
 
        /* Once the item is inserted at the bottom, push the 
        top element back to stack */
        push(top);
    }
}

void reverse() {
    if (!isEmpty()) {
        /* keep on popping top element of stack in 
        every recursive call till stack is empty  */
        int top = pop();
        reverse();
 
        /* Now, instead of inserting element back on top 
        of stack, we will insert it at the bottom of stack */
        insertAtBottom(top);
    }
}
/*
Returns the number of elements in Stack
*/
int getSize(){
 return st.top+1;
}

int main() {
 /* Initializing top index of stack */
    initialize(st);
    /* Adding elements in stack */
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    printf("Original Stack\n");
    printStack();
    reverse();
    printf("\nReversed Stack\n");
    printStack();
    return 0;
}
Output
Original Stack
 1 2 3 4 5
Reversed Stack
 5 4 3 2 1
Posted by
Labels: