Signup/Sign In

C Program To Reverse A Stack Using Recursion

learn c language tutorial

Logic To Reverse A Stack USing Recursion:

In this program stack elements are reversed using the recursion, all the elements are stored in the function stack one after another, once the stack becomes 0, insert an element at bottom, by inserting all the elements in the function stack in sequence.

Two user-defined functions are used

  • void insertatbottom()
  • void reverse()

insert at the bottom: This user-defined function inserts the numbers at bottom of the stack by using the recursion,

reverse: This user-defined function pop the elements and stores them in the function stack, The remaining stack is called recursively. Once all the stack elements are reversed, to insert the top elements at the bottom the insertatbottom() function is called.

Program To Reverse A Stack Using Recursion:

#include <stdio.h> 
#define MAX 7
#define TRUE 1
#define FALSE 0 
 
struct Stack {
    int top;
    int array[MAX];
} st;
 

void initialize() {
 st.top = -1;
}
 

int isFull() {   
    if(st.top >= MAX-1)
        return TRUE;
    else
        return FALSE;
}
 

int isEmpty() {
 if(st.top == -1)
     return TRUE;
 else
     return FALSE;
}
 

void push(int x) {
    if (isFull())
        printf("Stack is Full...\n");
    else {
        st.array[st.top + 1] = x;
        st.top++;
    }
}
 

int pop() {
    if (isEmpty())
        printf("Stack is Empty...\n");
    else {
     st.top = st.top - 1;
        return st.array[st.top+1];
    }
}
 
void printStack(){
 if(!isEmpty()){
     int temp = pop();
     printStack();
     printf(" %d ", temp);
     push( temp);
    }
}
void insertAtBottom(int y) {
    if (isEmpty()) {
        push(y);
    } else {
  
        
        int top = pop();
        insertAtBottom(item);
  
        
        push(top);
    }
}
 
void reverse() {
    if (!isEmpty()) {
        
        int top = pop();
        reverse();
  
        
        insertAtBottom(top);
    }
}

int getSize(){
 return st.top+1;
}
 
int main() {      
    initialize(st);
    push(0);
    push(9);
    push(4);
    push(6);
    push(7);
    printf("Given Input Stack\n");
    printStack();
    reverse();
    printf("\nReversed Given Input Stack\n");
    printStack();
    return 0;
}

Output:

Reverse