Problem.

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 merge(Queue q1, Queue 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 q1 = new Queue(); Queue q2 = new Queue(); 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; } }