import java.util.*;

public class MergeQueues {

    public static Queue<Integer> merge(Queue<Integer> q1, Queue<Integer> q2) {
        // creating a new queue to store the merged elements
        Queue<Integer> mergedQueue = new LinkedList<>();

        // merging until both q1 and q2 queues are empty
        while (q1.size() > 0 || q2.size() > 0) {
            // if q1 is empty then add all elements of q2 to the merged queue
            if (q1.size() == 0) {
                mergedQueue.add(q2.poll());
            } 
            // if q2 is empty then add all elements of q1 to the merged queue
            else if (q2.size() == 0) {
                mergedQueue.add(q1.poll());
            } 
            // comparing the smallest element of each queue and adding the smaller one to the merged queue
            else if (q1.peek() <= q2.peek()) {
                mergedQueue.add(q1.poll());
            } else {
                mergedQueue.add(q2.poll());
            }
            // poll is pulling and deleting the first element of the queue, this while loop continues till either queue is empty
        }

        return mergedQueue;
    }

    public static void main(String[] args) {
        // two queues of integers
        Queue<Integer> q1 = new LinkedList<>(Arrays.asList(1, 4, 11, 3, 5, 9, 8));
        Queue<Integer> q2 = new LinkedList<>(Arrays.asList(2, 4, 6, 3, 10));

        System.out.println("Q1: " + q1);
        System.out.println("Q2: " + q2);

        // merge the two queues using the merge method
        Queue<Integer> mergedQueue = merge(q1, q2);

        // converting the merged queue to a list and sort it by least to greatest or greatest to least
        List<Integer> sortedQ = new ArrayList<>(mergedQueue);
        Collections.sort(sortedQ);
        System.out.println("Merged queue in least to greatest: " + sortedQ);
        Collections.sort(sortedQ, Collections.reverseOrder());
        System.out.println("Merged queue in greatest to least: " + sortedQ);
    }
}

MergeQueues.main(null);
Q1: [1, 4, 11, 3, 5, 9, 8]
Q2: [2, 4, 6, 3, 10]
Merged queue in least to greatest: [1, 2, 3, 3, 4, 4, 5, 6, 8, 9, 10, 11]
Merged queue in greatest to least: [11, 10, 9, 8, 6, 5, 4, 4, 3, 3, 2, 1]