Implement the static method merge() in MergeQueues.java that takes two queues of
ID: 3939766 • Letter: I
Question
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;
}
}
Explanation / Answer
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