5

宿題のために、独自の PriorityQueue と PriorityQueueSort を実装する必要があります。ジェネリックを使用して、ソート機能なしで機能させましたが、今はここで立ち往生しています..

public static void PriorityQueueSort(Iterable<?> list, 
    PriorityQueue<?,?> pq) {
  if (!pq.isEmpty()) {
    throw new IllegalArgumentException("Non-Empty PriorityQueue");
  }

  for (Object obj : list) {

  }
}

リストと空の PriorityQueue を渡す必要があるため、これを行う方法についての私の最善の推測は上記のとおりです。不明なタイプのリストを反復処理し、そのリスト内の各要素を適切なタイプで優先度キューに追加できるようにするには、これをどのように攻撃すればよいですか?

編集：

十分な情報が含まれていないと判断されたため、いくつかの詳細を以下に示します。

カスタム PriorityQueue クラスと、K 型のキーと V 型の値を保持するカスタム Entry クラスがあります。

任意の型 T を持つ反復可能なリストを取得して反復処理し、各項目を取得して、最初は空の PriorityQueue に null 値のキーとして追加できるようにする必要があります。次に、PriorityQueue で removeMin() を継続的に呼び出し、それを同じリスト オブジェクトに順番に追加する必要があります。

public class PriorityQueue<K extends Comparable<? super K>,V> {

  private Entry<K,V> _head;
  private Entry<K,V> _tail;
  private int _size;

  public PriorityQueue() {
    this._head = null;
    this._tail = null;
    this._size = 0;
  }

  public int size() {
    return _size;
  }

  public boolean isEmpty() {
    return (size() == 0);
  }

  public Entry<K,V> min() {
    if (_head == null) {
      return null;
    }
    Entry<K,V> current = _head;
    Entry<K,V> min = _head;;

    while (current != null) {
      if (current.compareTo(min) < 0) {
        min = current;
      }
      current = current.getNext();
    }
    return min;
  }

  public Entry<K,V> insert(K k, V x) {
    Entry<K,V> temp = new Entry<K,V>(k,x);
    if (_tail == null) {
      _tail = temp;
      _head = temp;
    }
    else {
      _tail.setNext(temp);
      temp.setPrev(_tail);
      _tail = temp;
    }
    return temp;
  }

  public Entry<K,V> removeMin() {
    Entry<K,V> smallest = min();
    smallest.getPrev().setNext(smallest.getNext());
    smallest.getNext().setPrev(smallest.getPrev());

    return smallest;
  }

  public String toString() {
    return null;
  }

  public static <K> void PriorityQueueSort(Iterable<? extends K> list,
        PriorityQueue<? super K, ?> queue) {

      for (K item : list) {
          queue.insert(item, null);
      }

      list.clear();
  }

  public static void main(String[] args) {
    PriorityQueue<Integer, Integer> pq = 
        new PriorityQueue<Integer, Integer>();

    pq.insert(4, 2);
    pq.insert(5, 1);


    System.out.println(pq.min().toString());
  }
}
4

2 に答える 2

9

現時点で得られたものは、メソッド シグネチャの点では意味がありません。たとえば、aList<Button>と aを渡すことができます。PriorityQueue<String>

あなたは実際に次のようなものが欲しいと思います：

public static <T> void prioritySortQueue(Iterable<? extends T> iterable,
    PriorityQueue<? super T> queue) {

    for (T item : iterable) {
        queue.add(item);
    }
}

ここでの差異は柔軟性を高めるだけであることに注意してください。たとえば、List<Circle>butを使用することもできますが、それでもタイプセーフです。PriorityQueue<Shape>

編集:詳細が得られたので、次のようなものが必要だと思います:

public static <K> void prioritySortQueue(Iterable<? extends K> iterable,
    PriorityQueue<? super K, ?> queue) {

    for (T item : iterable) {
        queue.put(item, null);
    }
}

（メソッドがあると仮定します。クラスがputどのように見えるかはまだわかりません。）PriorityQueue

于 2013-03-08T13:55:23.503 に答える
3

タイプを参照できるように、メソッドをジェネリックにする必要があります。

public static <T> void PriorityQueueSort(Iterable<T> list, 
PriorityQueue<?,T> pq) {
于 2013-03-08T13:54:19.733 に答える