This C program demonstrates how to reverse a stack using recursion. A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Reversing a stack involves changing the order of its elements such that the top element becomes the bottom element, and so on.

Reversing a stack means changing the order of its elements so that the topmost element becomes the bottom-most and vice versa. One way to reverse a stack is by using recursion. Recursion is a programming technique where a function calls itself to solve a smaller subproblem. In the case of reversing a stack, the idea is to recursively pop all the elements from the stack, reverse the remaining stack, and then insert the popped element at the bottom of the reversed stack.

## Problem Statement

Write a C program to reverse a stack using recursion. Given a stack of integers, the program should reverse the order of its elements using recursion and display the reversed stack.

Input:

- The input is a stack of integers.

Output:

- The program should display the original stack and the reversed stack.

Constraints:

- The maximum number of elements in the stack is fixed at 100.
- The input stack may contain duplicates and can be empty.

## C Program to Reverse a Stack using Recursion

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 // Structure to represent a stack struct Stack { int arr[MAX_SIZE]; int top; }; // Function to initialize a stack void initialize(struct Stack *s) { s->top = -1; } // Function to check if the stack is empty int isEmpty(struct Stack *s) { return s->top == -1; } // Function to check if the stack is full int isFull(struct Stack *s) { return s->top == MAX_SIZE - 1; } // Function to push an element onto the stack void push(struct Stack *s, int data) { if (isFull(s)) { printf("Stack overflow!\n"); return; } s->arr[++(s->top)] = data; } // Function to pop an element from the stack int pop(struct Stack *s) { if (isEmpty(s)) { printf("Stack underflow!\n"); return -1; } return s->arr[(s->top)--]; } // Function to insert an element at the bottom of the stack void insertAtBottom(struct Stack *s, int data) { if (isEmpty(s)) { push(s, data); return; } int temp = pop(s); insertAtBottom(s, data); push(s, temp); } // Function to reverse a stack using recursion void reverseStack(struct Stack *s) { if (isEmpty(s)) return; int temp = pop(s); reverseStack(s); insertAtBottom(s, temp); } // Function to display the elements of the stack void display(struct Stack *s) { if (isEmpty(s)) { printf("Stack is empty!\n"); return; } printf("Stack elements: "); for (int i = 0; i <= s->top; i++) { printf("%d ", s->arr[i]); } printf("\n"); } // Main function int main() { struct Stack s; initialize(&s); push(&s, 1); push(&s, 2); push(&s, 3); push(&s, 4); push(&s, 5); printf("Original "); display(&s); reverseStack(&s); printf("Reversed "); display(&s); return 0; }

## How it Works

The program works by using recursion to reverse a stack. Here’s a step-by-step explanation of how it works:

- The program defines a structure called
`Stack`

, which represents the stack data structure. It has an array`arr`

to store the elements and a variable`top`

to keep track of the topmost element. - The program provides various functions to work with the stack:
`initialize`

: Initializes the stack by setting the top index to -1.`isEmpty`

: Checks if the stack is empty by comparing the top index with -1.`isFull`

: Checks if the stack is full by comparing the top index with the maximum size of the stack.`push`

: Pushes an element onto the stack. It first checks if the stack is full to avoid overflow.`pop`

: Pops and returns the top element from the stack. It first checks if the stack is empty to avoid underflow.`insertAtBottom`

: Inserts an element at the bottom of the stack using recursion. If the stack is empty, it directly pushes the element onto the stack. Otherwise, it recursively pops an element, calls itself to insert the element at the bottom of the remaining stack, and then pushes the popped element back onto the stack.`reverseStack`

: Reverses the stack using recursion. If the stack is empty, it returns. Otherwise, it pops the top element, recursively calls itself to reverse the remaining stack, and then inserts the popped element at the bottom of the reversed stack using the`insertAtBottom`

function.`display`

: Displays the elements of the stack.

- In the
`main`

function, the program creates a stack using the`initialize`

function. - It pushes some elements onto the stack using the
`push`

function. - The original stack is displayed using the
`display`

function. - The
`reverseStack`

function is called to reverse the stack using recursion. - The reversed stack is displayed using the
`display`

function.

By recursively popping elements from the original stack, reversing the remaining stack, and inserting the popped elements at the bottom of the reversed stack, the program effectively reverses the order of the elements in the stack.

The recursion continues until the stack is empty, and then the reversed stack is displayed.

## Input /Output

Explanation:

- The input stack contains the elements 5, 4, 3, 2, and 1 in the order they were inserted.
- The program displays the original stack as “5 4 3 2 1” using the
`display`

function. - Then, the program calls the
`reverseStack`

function to reverse the stack. - Inside the
`reverseStack`

function, the top element (5) is popped from the stack. - The function recursively calls itself with the remaining stack elements (4, 3, 2, and 1).
- The recursive call further pops the top element (4) and calls itself again with the remaining elements (3, 2, and 1).
- This process continues until the stack is empty.
- Now, the function starts inserting the popped elements at the bottom of the reversed stack using the
`insertAtBottom`

function. - The
`insertAtBottom`

function inserts the element 1 at the bottom of the empty stack. - The
`reverseStack`

function continues inserting the remaining elements (2, 3, 4, and 5) in reverse order. - Finally, the program displays the reversed stack as “1 2 3 4 5” using the
`display`

function.