Merge two std::queue in C++

Queue is a data structure that follows FIFO (first in first out) manner. In a queue, we can push values of similar (fixed for a queue) data type. If we try to pop an element then the element we pushed very first comes out and rest remains in the same order.

Now, we have two queues and we have to merge them.

Let’s have some examples to understand the task:

Example 1:
      queue 1 : 1 6 2 8 4
      queue 2 : 5 3 7 4 9
      merged queue : 1 5 6 3 2 7 8 4 4 9

Example 2:
      queue 1 : 4 8 1
      queue 2 : 3 6 2 9 4
      merged queue : 4 3 8 6 1 2 9 4

Example 3:
      queue 1 : 6 2 1 5 9 4
      queue 2 : 3 7 2 9
      merged queue : 6 3 2 7 1 2 5 9 9 4 

Merge two queues in C++

Approach:

We pop elements one by one and push them in the final queue. Suppose the size of both the queue is not the same then after popping some elements one of them will be empty. At this time all the elements of the non-empty queue are inserted in the final queue. Let’s jump into the code.

Code:

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

// function to print a queue
void print_queue(queue<int> q) {

    while(!q.empty()) {

        // pop elements one by one and print it
        cout << q.front() << " ";
        q.pop();
    }

    cout << "\n";
}

// function to merge two queues and return final queue
queue<int> merge_queues(queue<int> q1, queue<int> q2) {

    queue<int> merged_queue;

    // inserting in final queue
    while(!q1.empty() || !q2.empty()) {

        // inserting element of q1 if q1 is non-empty
        if(!q1.empty()) {
            merged_queue.push(q1.front());
            q1.pop();
        }

        // inserting element of q2 if q2 is non-empty
        if(!q2.empty()) {
            merged_queue.push(q2.front());
            q2.pop();
        }
    }

    return merged_queue;
}

int main() {
    queue<int> q1, q2;

    q1.push(4);
    q1.push(8);
    q1.push(1);
    // q1 becomes  ->  4 8 1

    q2.push(3);
    q2.push(6);
    q2.push(2);
    q2.push(9);
    q2.push(4);
    // q2 becomes  ->  3 6 2 9 4

    queue<int> result = merge_queues(q1, q2);

    print_queue(result);

    return 0;
}

Output:

4 3 8 6 1 2 9 4

Also read: Find Frequency of each element in an unsorted array in C++

Leave a Reply

Your email address will not be published. Required fields are marked *