[解決済み] JavaでBagを使用する理由

質問事項

現在、アルゴリズムとデータ構造について勉強しているのですが、「アルゴリズムの本4版」を読み返していたら Bag データ構造とともに Stack と Queue . その説明を読んだ後でも、私はまだ何が良いのか不明です。 Bag (これは remove() メソッド) のような他のデータ構造よりも優れています。 Stack , Queue , LinkedList または Set ? 私がBookから理解する限りでは、実装は Bag と同じです。 Stack の名前を置き換えるだけです。 push() を add() を削除し pop() メソッドを使用します。

という考え方があるんですね。 Bag は、基本的にアイテムを収集する機能を持ち、収集したアイテムを繰り返し、バッグが空かどうかをチェックし、その中のアイテムの数を見つけます。 しかし、どのような状況であれば Bag は、上記のCollectionsのいずれかを超えるものですか？また、なぜ Bag は remove() メソッドは、基本的に、何か特別な理由があるのでしょうか？

よろしくお願いします。

どのように解決するのですか？

Stack は、特定の削除順序 = LIFO (last-in-first-out)を持つ要素のコレクションのADTで、重複を許容します。

Queue は、特定の削除順序 = FIFO (first-in-first-out) で、重複を許容する要素のコレクションの ADT です。

LinkedList はリストの実装です。

Set は、重複を許さない要素の集まりのADTです。

Bag は、重複を許容する要素の集合のADTである。

一般に、ある要素を保持するものは Collection . 重複を許容するコレクションは Bag そうでない場合は Set . インデックス経由で要素にアクセスするバッグは List . 最後の要素の後に新しい要素を追加し、先頭（最初のインデックス）から要素を削除するメソッドを持つバッグは、次のようになります。 Queue . 最後の要素の後に新しい要素を追加し、末尾（最後のインデックス）から要素を削除するメソッドを持つバッグは、次のとおりです。 Stack .

例 Javaでは LinkedList は、コレクション、バッグ、リスト、キューであり、スタック操作をサポートしているので、スタックのように扱うことができます ( add ~ addLast ~ push , peekLast , removeLast ~ pop )なので、スタックも呼び出せます。その理由は スタック インターフェースは peek メソッドが予約されています。 キュー の実装は、リストの先頭（最初の要素）を取得するものです。したがって リンクリスト スタックメソッドは デク .

の有無 Bag を含む remove(Object) を実装するかどうかは、実装に依存します。 Bag 型はこの操作をサポートします。また get(int) 操作で、指定したインデックスのオブジェクトにアクセスすることができます。の時間的な複雑さは get(int) を実装することができます。 Bag リンクリストを使った場合は平均O(n/2)、サイズ変更可能な配列（array-list）を使った場合はインデックスで要素に直接アクセスできるのでO(1)となります。

しかし、その主な考え方は Bag は、このコレクションで複製と反復を可能にすることです。他の有用な操作をサポートするかどうかは、実装者の設計判断によります。

コレクションタイプのうちどれを使うかはニーズ次第で、重複を望まない場合は Set ではなく Bag . さらに、削除順序を気にするのであれば Stack または Queue であり、基本的には Bags を、特定の削除順序で削除します。以下のように考えることができます。 Bag のスーパータイプです。 Stack と Queue であり、特定の操作によってAPIを拡張するものである。

ほとんどの場合、オブジェクトを集めて何らかの処理をするだけです（反復処理＋要素処理）。そこで、最もシンプルな Bag を実装したもので、一方向のリンクリストである。