Hack 2

perform a merge or combination of 2 Queue's that are ordered. This is a foundation step for the algorithm used in Merge sorting. IMO, this algorithm is easier if you "peek" at data at the head of the queue, prior to performing dequeue action.

import java.util.LinkedList;
import java.util.Queue;

public class MergeQueues {
    public static void main(String[] args) {
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(1);
        q1.add(3);
        q1.add(5);

        Queue<Integer> q2 = new LinkedList<>();
        q2.add(2);
        q2.add(4);
        q2.add(6);

        Queue<Integer> mergedQueue = merge(q1, q2);

        // Print the merged queue
        while (!mergedQueue.isEmpty()) {
            System.out.print(mergedQueue.poll() + " ");
        }
    }

    public static Queue<Integer> merge(Queue<Integer> q1, Queue<Integer> q2) {
        Queue<Integer> mergedQueue = new LinkedList<>();

        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (q1.peek() < q2.peek()) {
                mergedQueue.add(q1.poll());
            } else {
                mergedQueue.add(q2.poll());
            }
        }

        // Add remaining elements of q1, if any
        while (!q1.isEmpty()) {
            mergedQueue.add(q1.poll());
        }

        // Add remaining elements of q2, if any
        while (!q2.isEmpty()) {
            mergedQueue.add(q2.poll());
        }

        return mergedQueue;
    }
}
MergeQueues.main(null)
1 2 3 4 5 6 

Description of the code

  • Java class called "MergeQueues" that merges the two sets of integers from least to greatest

  • two queues, "q1" and "q2," are created with integer values, and the "merge" method is called with "q1" and "q2" as arguments, and the returned merged queue is stored in "mergedQueue."

  • The merged queue is then printed out using a while loop that removes and prints the first element in the merged queue until the queue is empty.
  • The "merge" method creates a new empty queue called "mergedQueue"
  • It then compares the first elements of "q1" and "q2," removes the smaller element, and adds it to "mergedQueue"
  • This process continues until one of the input queues becomes empty
  • Then, the remaining elements of the non-empty queue are added to "mergedQueue" in their existing order. Finally, the mergedQueue is returned.
  • When the code is executed, it calls the "main" method, which in turn calls the "merge" method to merge "q1" and "q2" and print out the merged queue