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;
}
}

Solution

Hi, Friend, you have not posted details (methods )of Queue class, so I do not have any idea how to get all elements from queue without \'\'dequeing\' the elements.

Currently I have assumes \'front\', \'empty\' are the two methods of queue. According to this I have implemented your required method. In my implementation I am removing elements from Queue q1 and q2 because i do not know what is the methpd name in Queue class that gives me elements from queue one by one without removing from queue.

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) {

      

       Queue<Comparable> merged = new Queue<Comparable>();

      

       while(!q1.empty() && !q2.empty()){

          

           // if front of q1 is less or equal to front of q2

           if(q1.front().compareTo(q1.front()) <= 0 ){

               merged.enqueue(q1.dequeue());

           }

           else{

               merged.enqueue(q2.dequeue());

           }

       }

      

       // if q1 is not empty

       while(!q1.empty()){

           merged.enqueue(q1.dequeue());

       }

      

       // if q2 is not empty

       while(!q2.empty()){

           merged.enqueue(q2.dequeue());

       }

      

       return merged;

   }

   // 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;

   }

}

So, for correct implementation, please post Queue class.

But You can take an idea how to merge two sorted Queue from my implementation