Queue: Given a queue, interleave first half of the queue with second half

Problem Statement:

You are given a queue of even size.

You need to re arrange the queue by interleaving its firt half with second half.

Interleaving meaning, place first element from the first half and then first element

Example:

Input: Q = [1, 2, 3, 4]

Output: [1, 3, 2, 4]

Explanation:

Place the first element of 1st half "1", then place the 1st element of 2nd half "3". Repeat the steps.

Solution Explanation:

Solution is very simple.

Take a 2 temp queue, and move the first half into one queue and remaining into the other queue.

Then alternatively take the elements into the original queue and return the result.

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

Code Solution

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


void solution(queue<int>& res) 
{
    int n = res.size();
    queue<int> fh, sh;

    for (int i = 0; i < n / 2; i++) 
    {  
        fh.push(res.front());
        res.pop();
    }

    while (!res.empty()) 
    {
        sh.push(res.front());
        res.pop();
    }

    while (!fh.empty() && !sh.empty()) 
    {
        res.push(fh.front());
        fh.pop();
        
        res.push(sh.front());
        sh.pop();
    }
}

int main() 
{

    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    
    solution(q);
    
    while (!q.empty()) 
    {
        cout << q.front() << " ";
        q.pop();
    }

    return 0;
}

Output

1 3 2 4