59

Dequeデータ構造が必要な状況の例を教えてもらえますか？

注-は何であるか説明しないでくださいdeque？

4

8 に答える 8

50

Dequeは両端キューであり、両端からの挿入と削除が可能です。

実際のシナリオでは、チケット購入ラインに接続できます。キューのように機能しますが、ある時点で、ある団体がチケットを購入し、突然、キューの前で何かを尋ねるために戻ってきます。このシナリオでは、彼らはすでにチケットを購入しているので、来てさらに質問をする特権があります。したがって、この種のシナリオでは、要件に応じて前面からデータを追加するデータ構造が必要です。また、同じシナリオで、ユーザーはキューを後方から離れることもできます。

したがって、Dequeのデータ構造に完全に従います。

于 2013-02-23T07:28:21.390 に答える
27
  1. dequeの優れたアプリケーションは、Webブラウザの履歴を保存することです。最近アクセスしたURLが両端キューの前に追加され、両端キューの後ろにあるURLは、前に指定された回数挿入された後に削除されます。
  2. dequeのもう1つの一般的なアプリケーションは、ソフトウェアアプリケーションの元に戻す操作のリストを保存することです。
  3. dequeを使用できる1つの例は、A-Stealジョブスケジューリングアルゴリズムです。[5] このアルゴリズムは、複数のプロセッサのタスクスケジューリングを実装します。実行されるスレッドを含む個別の両端キューは、プロセッサごとに維持されます。次のスレッドを実行するために、プロセッサはdequeから最初の要素を取得します（「最初の要素の削除」deque操作を使用）。現在のスレッドが分岐した場合、それは両端キューの前に戻され（「前に要素を挿入」）、新しいスレッドが実行されます。プロセッサの1つが自身のスレッドの実行を終了すると（つまり、その両端キューが空になると）、別のプロセッサからスレッドを「盗む」ことができます。別のプロセッサの両端キューから最後の要素を取得し（「最後の要素を削除」）、実行します。それ。-礼儀ウィキペディア
于 2014-10-31T18:47:26.833 に答える
24

あらゆる種類の実際の待機ラインをモデル化する場合：エンティティ（ビット、人、車、単語、パーティクルなど）は、特定の頻度でラインの最後に到着し、ラインの最初に異なる頻度でサービスを提供します。待機中に、一部のエンティティが行を離れることを決定する場合があります...など。要点は、行の両端で挿入/削除するための「高速アクセス」が必要であるため、両端キューです。

于 2010-10-07T10:07:31.290 に答える
8

ウィキペディアの例

dequeを使用できる1つの例は、A-Stealジョブスケジューリングアルゴリズムです。このアルゴリズムは、複数のプロセッサのタスクスケジューリングを実装します。実行されるスレッドを含む個別の両端キューは、プロセッサごとに維持されます。次のスレッドを実行するために、プロセッサはdequeから最初の要素を取得します（「最初の要素の削除」deque操作を使用）。現在のスレッドが分岐した場合、それは両端キューの前に戻され（「前に要素を挿入」）、新しいスレッドが実行されます。プロセッサの1つが自身のスレッドの実行を終了すると（つまり、その両端キューが空になると）、別のプロセッサからスレッドを「盗む」ことができます。別のプロセッサの両端キューから最後の要素を取得し（「最後の要素を削除」）、実行します。それ。

最近のCLRviaC＃の本で、Richterは.Net4.0でThreadPoolに加えられた改善について説明しています。特に仕事を盗むことについては、間違いなく読む価値があります。Richterによって記述されたアルゴリズムは、Wikipediaの例と非常によく似ているため、Dequeもそこで使用されていると思います。

于 2010-10-07T09:46:48.610 に答える
2

http://en.wikipedia.org/wiki/Dequeによると、dequeを使用するジョブスケジューリングアルゴリズムがあります。ドイツ語版ウィキペディアのページ（http://de.wikipedia.org/wiki/Deque）では、パターンマッチングアルゴリズムと、両端キューの使用例としての非決定論的有限状態マシンの実装について説明しています。

于 2010-10-07T09:40:09.370 に答える
0

「キュー」は、2つのデータ構造のいずれかを使用して実装できます

  1. リンクリスト-もしあなたがもっぱら端で作業していて、メモリ割り当てのオーバーヘッドを気にしない（またはメモリをどのように割り当てることができるかについて制約されている）場合、これは理にかなっています。
  2. deque-両端で作業する場合は、位置アクセスも必要であり（または、キュー内のアイテムをすばやく反復処理する機能）、メモリ割り当てのオーバーヘッドが重要です（ただし、制約はありません）。dequeは、両方の長所を提供します（割り当てのようなベクトル）。機能のようなリンクリストを使用すると、とにかく最後に、中央に挿入する方が高価です）

通常、dequeは優先キューに役立ちます。キューのスキャンは、リンクリストよりもdequeの方がはるかに高速です。

于 2010-10-07T10:05:18.347 に答える
0

dequeは、車が線路の左側または右側で出入りできる駅をモデル化できますが、出入りできるのは両端の車だけです。これは、内側の車が外側の車にぶつかって出て行けないため、待つ必要があるためです。

于 2015-03-05T19:02:02.713 に答える
0

イテレータをチェーンする場合の実際の使用例があります。拡張可能なイテレータを実装するために使用しました：

import java.util.Deque;
import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedDeque;

public class ExtendableIterator<T> implements Iterator<T> {

    public Deque<Iterator<T>> its = new ConcurrentLinkedDeque<Iterator<T>>();

    public ExtendableIterator() {

    }

    public ExtendableIterator(Iterator<T> it) {
        this();
        this.extend(it);
    }

    @Override
    public boolean hasNext() {
        // this is true since we never hold empty iterators
        return !its.isEmpty() && its.peekLast().hasNext();
    }

    @Override
    public T next() {
        T next = its.peekFirst().next();
        if (!its.peekFirst().hasNext()) {
            its.removeFirst();
        }
        return next;
    }

    public void extend(Iterator<T> it) {
        if (it.hasNext()) {
            its.addLast(it);
        }
    }
}
于 2015-11-25T16:42:46.130 に答える