Question

I m trying to write a method that will take in two Queues (pre-sorted Linked Lists) and return the merged, in ascending order, resulting Queue object. I pasted the Queue class, the merge method starts 1/2 way down.

I m having trouble calling merge, this is how I am trying to call it from my main method, can anyone help with this call with new1 and new2. Thanks so much Everyone!

Please let me know if anyone notices anything else out of place. Thanks!

///////////////// //Testing with a call of merge method & 2 Queues///////////////////

public class test {
public static void main (String args[]){


 Queue new1 = new Queue();
 new1.enqueu(1);
 new1.enqueu(3);
 new1.enqueu(5);

 Queue new2 = new Queue();
 new1.enqueu(2);
 new1.enqueu(4);
 new1.enqueu(6);

    merge(new1, new2);

 //How to call merge? Queue.merge(new1, new2)???
/////////////////Queue/Merge method below////////////////////////


public class Queue {
private Node first, last;
public Queue(){
first = null;
last = null;
}

public void enqueu(int n){
 Node newNode = new Node(n);
 if (first == null)
 {
  first = newNode;
  last = newNode;

 }
 else
 {
  last.setNext(newNode);
  last = newNode;
 }
 }



public int dequeue(){
int num = first.getNum();
first = first.getNext();
if(first == null)
last = null;
return num;
}

public Boolean isEmpty() { return first == null; }



////////////////////////Begin Queue merge/////////////////////////////////


Queue merge(Queue q1, Queue q2) {
 Queue result = new Queue();
 boolean q1empty = q1.isEmpty();
 boolean q2empty = q2.isEmpty();
 while (!(q1empty || q2empty)) { 
 if (q1.first.getNum() < q2.first.getNum()) {
 result.enqueu(q1.dequeue());
 q1empty = q1.isEmpty();
 } else {
 result.enqueu(q2.dequeue());
 q2empty = q2.isEmpty();
 }
 }
 if (!q1empty) {
 do {
 result.enqueu(q1.dequeue());
 } while (!q1.isEmpty());
 } else if (!q2empty) {
 do {
 result.enqueu(q2.dequeue());
 } while (!q2.isEmpty());
 }
 return result;
 }}

Answer 1

You have what appears to be a bug here:

Queue new1 = new Queue();
new1.enqueu(1);
new1.enqueu(3);
new1.enqueu(5);

Queue new2 = new Queue();
new1.enqueu(2);
new1.enqueu(4);
new1.enqueu(6);

You ve added six elements to new1 and zero to new2.

Since your merge method is an instance method of the Queue class, you need to call it on an instance of Queue, such as

Queue q = new Queue();
Queue merged = q.merge(new1, new2);

However since merge appears to have no side-effects and does not alter any state of the Queue instance, you probably want to just make this method static so that it belongs to the Queue class and not an instance of Queue. For example:

static Queue merge(Queue q1, Queue q2) {
     ...
}

//in main()...
Queue merged = Queue.merge(new1, new2);

Answer 2

A simple approach to merging two sorted Iterators into another Iterator:

public static Iterator<Object> merge(final Iterator<Object> it1,
        final Iterator<Object> it2, final Comparator<Object> comp) {
    return new Iterator<Object>() {
        private Object o1 = it1.hasNext() ? it1.next() : null, o2 = it2
                .hasNext() ? it2.next() : null;
            @Override
        public boolean hasNext() {
            return o1 != null || o2 != null;
        }

        @Override
        public Object next() {
            if (o1 == null && o2 == null)
                throw new NoSuchElementException();
            Object ret;
            if (o1 == null) {
                ret = o2;
                o2 = it2.hasNext() ? it2.next() : null;
            } else if (o2 == null) {
                ret = o1;
                o1 = it1.hasNext() ? it1.next() : null;
            } else {
                if (comp.compare(o1, o2) <= 0) {
                    ret = o1;
                    o1 = it1.hasNext() ? it1.next() : null;
                } else {
                    ret = o2;
                    o2 = it2.hasNext() ? it2.next() : null;
                }
            }
            return ret;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not implemented");
        }
    };
}

友情链接