Queue: Given a queue, reverse it

Problem Statement:

You are given a queue, you need to reverse it by using below operations of the queue.

enqueue(n)
dequeue()
empty()

Example:

Input: q = [1, 2, 3, 4]
Output: q = [4, 3, 2, 1]

Solution 1:

We will use stack to solve this problem.

Pop the elements into the queue and insert into the stack.

Then pop form stack and insert into the queue. We get the result.

Time Complexity: O(n)
Space Complexity: O(n)

Solution 2: Using recursion

In this approach, pop the element from the queue.

Then push the popped element into the resultant queue.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

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

void solution_1(queue<int>& q) 
{

    stack<int> st;
    
    while (!q.empty()) 
    {
        st.push(q.front());
        q.pop();
    }

    while (!st.empty()) 
    {
        q.push(st.top());
        st.pop();
    }
}

void solution_2 (queue<int>& q) 
{

    if (q.empty()) return;

    int front = q.front();
    q.pop();

    solution_2(q);

    q.push(front);
}

int main() 
{

    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
   
    solution_1 (q);
    
    cout<<"Solution 1 = "<<endl;

    while (!q.empty()) 
    {
        cout << q.front() << " ";
        q.pop();
    }

    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    
    solution_2 (q);
    
    cout<<"\nSolution 2 = "<<endl;

    while (!q.empty()) 
    {
        cout << q.front() << " ";
        q.pop();
    }
}

Output

Solution 1 = 
4 3 2 1 
Solution 2 = 
4 3 2 1