Problem Statement

Given a stack of integers, your task is to reverse the stack using only recursion. You are not allowed to use any additional data structures like arrays or queues. Only stack operations (push, pop, isEmpty, etc.) and recursion can be used to accomplish the reversal.

Examples

Example 1:

Input:
    |  1  | <- Top of stack
    |  2  |
    |  3  |
    |  4  |
    |  5  | <- Bottom of stack
    +-----+

Output:
    |  5  | <- Top of stack
    |  4  |
    |  3  |
    |  2  |
    |  1  | <- Bottom of stack
    +-----+

Example 2:

Input:
    |  10  | <- Top of stack
    |  20  |
    |  30  |
    |  40  | <- Bottom of stack
    +------+

Output:
    |  40  | <- Top of stack
    |  30  |
    |  20  |
    |  10  | <- Bottom of stack
    +------+

Code:

#include <iostream>
#include <stack>
using namespace std;

// Function to insert an element at the bottom of a stack
void insertAtBottom(stack<int>& s, int element) {
    if (s.empty()) {  // Base case: If stack is empty, push the element
        s.push(element);
        return;
    }

    // Pop the top element and hold it
    int topElement = s.top();
    s.pop();

    // Recursive call to insert element at the bottom
    insertAtBottom(s, element);

    // Push the held element back onto the stack
    s.push(topElement);
}

// Function to reverse the stack
void reverseStack(stack<int>& s) {
    if (s.empty()) {  // Base case: If stack is empty, return
        return;
    }

    // Pop the top element
    int topElement = s.top();
    s.pop();

    // Recursive call to reverse the remaining stack
    reverseStack(s);

    // Insert the popped element at the bottom of the reversed stack
    insertAtBottom(s, topElement);
}

// Helper function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    cout << "Original Stack:" << endl;
    printStack(s);

    // Re-create stack for reversing it (for demonstration purposes)
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    // Reverse the stack
    reverseStack(s);

    cout << "Reversed Stack:" << endl;
    printStack(s);

    return 0;
}