Problem Statement:

You are given a queue of integers, and you need to reverse the order of the elements in the queue.

Example:

• Input: queue = [10, 20, 30, 40, 50]
• Output: queue = [50, 40, 30, 20, 10]

We can solve this using two approaches: the Recursive Approach and the Stack Approach.

Now, let’s break down the two approaches!

1. Recursive Approach:

The idea here is to use recursion to reverse the queue. The key is to think about how recursion works , putting elements back in the queue in reverse order.

Step-by-Step Explanation:

1. Base Case:
   • If the queue is empty, we simply return. There's nothing to reverse.
2. Recursive Step:
   • Remove the front element of the queue and store it.
   • Recursively reverse the remaining elements in the queue.
   • Once the recursion is done, add the stored element back to the queue.

This way, when the recursion unwinds, elements are added back in reverse order.

Code Implementation:

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

void reverseQueueRecursively(queue<int>& q) {
    // Base case: If the queue is empty, return
    if (q.empty()) {
        return;
    }

    // Step 1: Remove the front element and store it
    int frontElement = q.front();
    q.pop();

    // Step 2: Recursively reverse the remaining queue
    reverseQueueRecursively(q);

    // Step 3: Add the stored element back to the queue
    q.push(frontElement);
}

void printQueue(queue<int> q) {
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    q.push(40);
    q.push(50);

    cout << "Original Queue: ";
    printQueue(q);

    reverseQueueRecursively(q);

    cout << "Reversed Queue (using recursion): ";
    printQueue(q);

    return 0;
}

How the Recursion Works:

• First Call: The queue [10, 20, 30, 40, 50] pops 10 and recurses with [20, 30, 40, 50].
• Second Call: Pops 20 and recurses with [30, 40, 50].
• This continues until the queue is empty.
• Unwinding: Once empty, 50 is pushed back, then 40, 30, 20, and finally 10, effectively reversing the queue.

2. Stack Approach:

The stack approach leverages the Last-In-First-Out (LIFO) property of stacks. By pushing all elements of the queue onto the stack, we reverse their order, and when we pop elements back into the queue, they come out in reversed order.

Step-by-Step Explanation:

1. Push Elements to Stack:
   • Iterate through the queue, popping elements from the front and pushing them onto a stack.
   • Since the stack reverses the order, the last element of the queue becomes the first on the stack.
2. Pop Elements Back to Queue:
   • Now, pop each element from the stack and push it back into the queue.
   • This step puts the elements back in reversed order.

Code Implementation:

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

void reverseQueueWithStack(queue<int>& q) {
    stack<int> s;

    // Step 1: Push all elements of the queue onto the stack
    while (!q.empty()) {
        s.push(q.front());
        q.pop();
    }

    // Step 2: Pop all elements from the stack back to the queue
    while (!s.empty()) {
        q.push(s.top());
        s.pop();
    }
}

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    q.push(40);
    q.push(50);

    cout << "Original Queue: ";
    printQueue(q);

    reverseQueueWithStack(q);

    cout << "Reversed Queue (using stack): ";
    printQueue(q);

    return 0;
}

How the Stack Approach Works:

• Stack: Initially empty,
• it will push 10, 20, 30, 40, 50 from the queue. Now the stack is [50, 40, 30, 20, 10].
• Queue: After popping from the stack, the queue becomes [50, 40, 30, 20, 10].

Final Thoughts:

• Both approaches have their use cases. The recursive approach is elegant and showcases the power of recursion, though it might not be optimal for very large queues due to stack overflow concerns.
• The stack approach is straightforward and leverages the stack's natural LIFO behavior, making it a more iterative solution.

Feel free to use either method based on your comfort level and the problem constraints.

Happy coding ! Doshthh 🚀