Java Queue Merge, Beginner

Question

J'essaye d'écrire une méthode qui prendra deux files d'attente (listes liées pré-triées) et renverra l'ordre fusionné, dans l'ordre croissant, l'objet de file d'attente résultant. J'ai collé la classe file d'attente, la méthode de fusion commence 1/2 fois plus bas.

J'ai des problèmes pour appeler la fusion, c'est ainsi que j'essaie de l'appeler depuis ma méthode principale , quelqu'un peut-il m'aider avec cet appel avec new1 et new2. Merci beaucoup Tout le monde!

S'il vous plaît laissez-moi savoir si quelqu'un remarque quelque chose d'autre à sa place. Merci!

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

Vous avez ce qui semble être un bug ici:

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

Vous avez ajouté six éléments à new1 et zéro à new2.

Depuis votre méthode merge est une méthode d'instance de la classe Queue, vous devez appeler sur une instance de file d'attente, comme

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

Cependant, depuis la fusion ne semble pas avoir d'effets secondaires et ne modifier tout état de l'instance de la file d'attente, vous voulez probablement rendre cette méthode statique afin qu'elle appartienne à la classe de la file d'attente et non à une instance de file d'attente. Par exemple:

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

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

Answer 2

Une approche simple de la fusion de deux itérateurs triés dans un autre 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"); 
     } 
    }; 
}