Problem. Implement the static method merge() in MergeQueues.java that takes two
ID: 3739907 • Letter: P
Question
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<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
Since 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 assumed 'peek', 'isEmpty' are the two methods of 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.isEmpty() && !q2.isEmpty()){
// if front of q1 is less or equal to front of q2
if(q1.peek().compareTo(q2.peek()) <= 0 ){
merged.enqueue(q1.dequeue());
}
else{
merged.enqueue(q2.dequeue());
}
}
// if q1 is not empty
while(!q1.isEmpty()){
merged.enqueue(q1.dequeue());
}
// if q2 is not empty
while(!q2.isEmpty()){
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;
}
}
Thanks, let me know if there is any concern. PLEASE RATE
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.