Implement the static method merge in MergeQueuesjava that ta

Implement the static method merge() in MergeQueues.java that takes two queues of sorted
items as arguments and returns a queue that results from merging the queues into sorted order. Your implementation must
be linear and must not alter the input queues.

Result:

$ java MergeQueues

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Code:

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import java.util.Iterator;

public class MergeQueues {
// Return true if v is less than w and false otherwise.
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

// Merge and return the two sorted queues as a single sorted queue.
private static Queue<Comparable> merge(Queue<Comparable> q1, Queue<Comparable> q2) {
.......................................................................................... <- I have to write this
}

// Test client. [DO NOT EDIT]
public static void main(String[] args) {
String[] a = {\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\", \"I\",
\"J\", \"K\", \"L\", \"M\", \"N\", \"O\", \"P\", \"Q\", \"R\",
\"S\", \"T\", \"U\", \"V\", \"W\", \"X\", \"Y\", \"Z\"};
Queue<Comparable> q1 = new Queue<Comparable>();
Queue<Comparable> q2 = new Queue<Comparable>();
for (String s : a) {
if (StdRandom.bernoulli(0.5)) {
q1.enqueue(s);
}
else {
q2.enqueue(s);
}
}
int s1 = q1.size(), s2 = q2.size();
StdOut.println(merge(q1, q2));
assert q1.size() == s1 && q2.size() == s2;
}
}

http://introcs.cs.princeton.edu/java/43stack/Queue.java.html Here is the Queue class

Solution

int e1 = q1.dequeue(); int e2 = q2.dequeue(); while (true) { if (e1 < e2) { merged.enqueue(e1); if (q1.isEmpty()) { // add remaining q2 elements while (!q2.isEmpty()) { merged.enqueue(q2.dequeue()); } break; } // take another element from q1 e1 = q1.dequeue(); } else { merged.enqueue(e2); if (q2.isEmpty()) { // add remaining q1 elements while (!q1.isEmpty()) { merged.enqueue(q1.dequeue()); } break; } // take another element from q2 e2 = q2.dequeue(); } }