Java隊列合併，初學者

Question

我想寫一個方法，將採取兩個隊列（預先排序的鏈接列表）並返回合併，以升序排列結果隊列對象。我粘貼隊列類，合併方法開始1/2下降。

我在調用合併時遇到了困難，這就是我如何從我的主要方法中調用它，任何人都可以用new1和new2來協助這個調用。非常感謝大家！

請讓我知道是否有人注意到任何不合適的地方。謝謝！

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

你有什麼似乎是這裏的錯誤：

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

你添加了六個要素new1和零new2。

由於您的merge方法是Queue類的實例方法，你需要調用它隊列的實例，如

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

但是因爲合併似乎沒有任何副作用和不改變隊列實例的任何狀態，你可能只想使這個方法是靜態的，這樣它就屬於隊列類而不是隊列的一個實例。例如：

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

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

Answer 2

一種簡單的方法來合併兩個已排序的迭代器到另一個迭代：

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