Java Merging Two Sorted Queues in Ascending Order

A sorted queue means the items in this queue are in descending order or ascending order. If we insert the items into a new queue one by one and keep the previous order, the new queue should also be sorted.

Question

4.3.42 Merging two sorted queues. Given two queues with strings in ascending order, move all of the strings to a third queue so that the third queue ends up with the strings in ascending order.

Computer Science An Interdisciplinary Approach (2016, page 260).

Implementing Steps

This time, we are going to implement queues based on java.util.Queue instead of the Queue created by ourself. The queue interface from java util uses add method to enqueue a new item, uses poll to dequeue an existing item and uses peek to retrieve the value at the head of the queue, but without removing that item.

Here goes the key steps:

1. There are two sorted queues A, B, and an empty queue C.
2. Peek two items from A, B if not empty.
3. Poll and Insert the greater value to the empty queue.
4. Return to step 2.
5. Insert the remaining items into C if A or B is not empty.

Solution

/******************************************************************************
 *  Compilation:  javac MergingTwoSortedQueues.java
 *  Execution:    java MergingTwoSortedQueues
 *
 *  Merging two ascending sorted queues to one queue with ascending order.
 *
 *  % java MergingTwoSortedQueues
 *  First queue:
 *  [a, b, g, h]
 *
 *  Second queue:
 *  [A, c, d, e, f]
 *
 *  Merged queue:
 *  [A, a, b, c, d, e, f, g, h]
 *
 ******************************************************************************/
import java.util.Queue;
import java.util.PriorityQueue;

class MergingTwoSortedQueues {
    public static void main(String[] args) {
        Queue first = new PriorityQueue<String>();
        Queue second = new PriorityQueue<String>();

        first.add("a");
        first.add("b");
        first.add("g");
        first.add("h");

        second.add("A");
        second.add("c");
        second.add("d");
        second.add("e");
        second.add("f");

        System.out.println("First queue: ");
        System.out.println(first.toString());
        System.out.println("\nSecond queue: ");
        System.out.println(second.toString());

        Queue result = MergingTwoSortedQueues.merge(first, second);

        System.out.println("\nMerged queue: ");
        System.out.println(result.toString());
    }

    public static Queue<String> merge(Queue<String> first, Queue<String> second) {
        Queue<String> mergedQueue = new PriorityQueue<String>();

        // If both queues are not empty.
        while (!first.isEmpty() && !second.isEmpty()) {
            String left = first.peek();
            String right = second.peek();

            if (left.compareTo(right) < 0) {
                mergedQueue.add(first.poll());
            } else {
                mergedQueue.add(second.poll());
            }
        }

        // If there are remaining items in one of the queue.
        while (!first.isEmpty()) {
            mergedQueue.add(first.poll());
        }

        while (!second.isEmpty()) {
            mergedQueue.add(second.poll());
        }

        return mergedQueue;
    }
}

Output

-> javac MergingTwoSortedQueues.java
Note: MergingTwoSortedQueues.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

-> java MergingTwoSortedQueues
First queue:
[a, b, g, h]

Second queue:
[A, c, d, e, f]

Merged queue:
[A, a, b, c, d, e, f, g, h]

The time complexity of merging two sorted queues in this implementation is Θ(n).