Merging two queues in C++ can be a handy operation when working with data structures. In this article, we’ll explore how to merge two queues efficiently using the standard library.

Queue Basics

Before we dive into merging queues, let’s briefly review the concept of a queue. A queue is a data structure that follows the First-In-First-Out (FIFO) order, meaning the element that gets added first will be the first one to be removed.

In C++, you can use the std::queue container from the <queue> header to implement a queue. It provides convenient methods like push, pop, front, and empty to manipulate the queue.

Merging Two Queues

To merge two queues, we need to transfer all the elements from one queue to another while maintaining the original order. The std::queue container doesn’t provide a direct method for merging two queues, but we can accomplish this by using a temporary queue.

Here’s an example of how you can merge two queues in C++:

#include <iostream>
#include <queue>

std::queue<int> mergeQueues(std::queue<int>& queue1, std::queue<int>& queue2) {
    std::queue<int> mergedQueue;

    while (!queue1.empty() && !queue2.empty()) {
        if (queue1.front() <= queue2.front()) {
            mergedQueue.push(queue1.front());
            queue1.pop();
        } else {
            mergedQueue.push(queue2.front());
            queue2.pop();
        }
    }

    // Transfer remaining elements from queue1, if any
    while (!queue1.empty()) {
        mergedQueue.push(queue1.front());
        queue1.pop();
    }

    // Transfer remaining elements from queue2, if any
    while (!queue2.empty()) {
        mergedQueue.push(queue2.front());
        queue2.pop();
    }

    return mergedQueue;
}

int main() {
    std::queue<int> queue1;
    std::queue<int> queue2;

    // Adding elements to queue1
    queue1.push(5);
    queue1.push(10);
    queue1.push(15);

    // Adding elements to queue2
    queue2.push(3);
    queue2.push(8);
    queue2.push(12);

    std::queue<int> mergedQueue = mergeQueues(queue1, queue2);

    std::cout << "Merged Queue: ";
    while (!mergedQueue.empty()) {
        std::cout << mergedQueue.front() << " ";
        mergedQueue.pop();
    }

    return 0;
}

In this example, we define a function mergeQueues that takes two queues (queue1 and queue2) as parameters and returns a new merged queue. We iterate over both queues, comparing the front elements and pushing the smaller element to the merged queue. Once one queue becomes empty, we transfer the remaining elements from the other queue.

Finally, we test the mergeQueues function by creating two queues and adding some elements to them. The merged queue is then printed to the console for verification.

Conclusion

Merging two queues in C++ can be efficiently achieved by leveraging the standard library’s std::queue container and a temporary queue. By following the logic outlined in this article, you can easily merge queues while maintaining the original order of elements.

Hashtags: #C++ #queue