76

私は（Javaで）画像のピクセルを中心点から外側に再帰的にトラバースする再帰的な画像処理アルゴリズムに取り組んでいます。

残念ながら、これによりスタック オーバーフローが発生します。そこで、Queue ベースのアルゴリズムに切り替えることにしました。

さて、これはすべて問題なくダンディーですが、予測可能な状態を維持せずに、そのキューが非常に短い時間で数千のピクセルを分析し、常にポップしてプッシュするという事実を考慮すると (長さ 100 の間のどこかになる可能性があります)。および 20000)、キューの実装には、非常に高速なポップおよびプッシュ機能が必要です。

リンクされたリストは、リスト内の他の要素を再配置せずに要素を自分自身にプッシュできるため、魅力的に見えますが、十分に高速であるためには、先頭と末尾 (または 2 番目の要素) の両方に簡単にアクセスできる必要があります。 -二重にリンクされていない場合は最後のノード)。悲しいことに、Java での連結リストの基礎となる実装に関連する情報を見つけることができないため、連結リストが本当に進むべき道であるかどうかを判断するのは困難です...

これは私の質問につながります。私がやろうとしていることに対して、Java での Queue インターフェースの最良の実装は何でしょうか? (キューの先頭と末尾以外のものを編集したり、アクセスしたりしたくありません。並べ替えなどはしたくありません。反対に、私は多くのプッシュを行うつもりです。とポップし、キューのサイズがかなり変化するため、事前割り当ては非効率的です）

4

9 に答える 9

82

使用する：

Queue<Object> queue = new LinkedList<>();

.offer(E e)キューの最後に要素を追加したり、キュー.poll()の先頭（最初の要素）をデキューして取得したりするために使用できます。

Javaがインターフェースを定義しQueue、LinkedListが実装を提供しました。

.getFirst()また、Head要素とTail要素への参照も保持します。これらは、それぞれとで取得できます.getLast()。


キューインターフェイスを提案してくれた@Snicolasの功績

于 2012-06-22T03:29:31.883 に答える
48

LinkedList を使用する場合は注意してください。次のように使用する場合:

LinkedList<String> queue = new LinkedList<String>();

最初以外の要素を削除する可能性があるため、キュー定義に違反する可能性があります（LinkedListにはそのようなメソッドがあります）。

しかし、次のように使用する場合:

Queue<String> queue = new LinkedList<String>();

これは、挿入は後ろでのみ、削除は前でのみ行う必要があるというユーザーへの注意事項であるため、問題ありません。

問題のあるメソッドの UnsupportedOperationException をスローする PureQueue クラスに LinkedList クラスを拡張することにより、Queue インターフェースの不完全な実装を克服できます。または、タイプ LinkedList オブジェクト、リストであるフィールドを 1 つだけ持つ PureQueue を作成することによって、集約を使用してアプローチすることもできます。唯一のメソッドは、デフォルト コンストラクター、コピー コンストラクターisEmpty()、、、、、およびです。これらのメソッドはすべてワンライナーにする必要があります。次に例を示します。size()add(E element)remove()element()

/**
* Retrieves and removes the head of this queue.
* The worstTime(n) is constant and averageTime(n) is constant.
*
* @return the head of this queue.
* @throws NoSuchElementException if this queue is empty.
*/
public E remove()
{
    return list.removeFirst();
} // method remove()
于 2014-02-08T13:58:10.110 に答える
12

両端での挿入/削除を提供するDequeインターフェイスを確認してください。LinkedList はそのインターフェイスを実装していますが (前述のとおり)、使用する場合は ArrayDeque の方が適している場合があります。各ノードに一定のオブジェクトを割り当てるコストが発生しません。繰り返しになりますが、どの実装を使用するかは問題ではありません。

通常のポリモーフィズムの良さが発揮されます。特定の実装ではなく、Deque インターフェースに対して記述することの利点は、実装を簡単に切り替えて、どの実装が最適かをテストできることです。その中の行を変更するだけnewで、残りのコードは同じままです。

于 2012-06-22T04:43:26.413 に答える
2

私はあなたが実装のような単純なものでいくらかできると思います

package DataStructures;

public class Queue<T> {

   private Node<T> root;

   public Queue(T value) {
      root = new Node<T>(value);
   }

   public void enque(T value) {
      Node<T> node = new Node<T>(value);
      node.setNext(root);
      root = node;
   }

   public Node<T> deque() {

      Node<T> node = root;
      Node<T> previous = null;

      while(node.next() != null) {
         previous = node;
         node = node.next();
      }
      node = previous.next();
      previous.setNext(null);
      return node;
   }

   static class Node<T> {

      private T value;
      private Node<T> next;

      public Node (T value) {
         this.value = value;
      }

      public void setValue(T value) {
         this.value = value;
      }

      public T getValue() {
         return value;
      }

      public void setNext(Node<T> next) {
         this.next = next;
      }

      public Node<T> next() {
         return next;
      }
   }
}
于 2013-01-29T19:53:41.613 に答える
2

キュー内の可能なアイテム数の上限がわかっている場合、LinkedListはキュー内の各アイテムのオブジェクト（リンク）を作成するため、循環バッファーはLinkedListよりも高速です。

于 2012-06-22T03:44:11.653 に答える