在 Java 中使用 Bag 的原因

我目前正在学习算法和数据结构，当我阅读《算法之书》第四版时，我发现了Bag数据结构与Stack and Queue。 阅读了它的解释后，我仍然不清楚为什么我更喜欢使用Bag（其中没有remove()方法）优于其他数据结构，例如Stack, Queue, LinkedList or a Set？ 据我从书中可以理解，实施Bag，与 a 相同Stack，只需替换名称push() to add()并删除pop() method.

所以一个想法是Bag基本上具有收集物品的能力，然后迭代收集的物品，检查袋子是否为空并找到其中物品的数量。 但在什么情况下我最好使用Bag超过上述集合之一？以及为什么一个Bag没有remove()基本上方法？有什么具体原因吗？

提前致谢。

Stack是具有特定删除顺序的元素集合的 ADT = LIFO（后进先出），允许重复，

Queue是具有特定删除顺序的元素集合的 ADT = FIFO（先进先出），允许重复，

LinkedList是清单的实施，

Set是不允许重复的元素集合的 ADT，

Bag是允许重复的元素集合的 ADT。

一般来说，任何包含元素的东西都是Collection。 任何允许重复的集合都是Bag，否则就是Set。 任何通过索引访问元素的包都是List。 在最后一个元素之后追加新元素并具有从头部（第一个索引）删除元素的方法的 Bag 是Queue。 在最后一个元素之后追加新元素并具有从尾部（最后一个索引）删除元素的方法的 Bag 是Stack.

示例：在 Java 中，链表 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html是一个集合、包、列表、队列，您也可以像堆栈一样使用它，因为它支持堆栈操作（add~addLast~push, peekLast, removeLast~pop），所以你也可以称它为堆栈。原因，为什么它没有实施Stack https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html接口是peek方法被保留Queue https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html检索列表头部（第一个元素）的实现。因此，如果链表 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html，“堆栈方法”源自Deque https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html.

Whether Bag包含remove(Object)或不可能取决于实施 e。 G。你可以实现你自己的Bag支持此操作的类型。您也可以实施get(int)访问指定索引上的对象的操作。的时间复杂度get(int)将取决于您的实施 e。 G。一个可以实施Bag通过链表，因此复杂度平均为 O(n/2)，另一种通过可调整大小的数组（数组列表），通过索引直接访问元素，因此复杂度为 O(1)。

但其主要思想是Bag也就是说，它允许对该集合进行重复和迭代。它是否支持其他有用的操作取决于实现者的设计决策。

使用哪一种集合类型取决于您的需要，如果不需要重复，您可以使用Set代替Bag。此外，如果您关心删除订单，您会选择Stack or Queue基本上是Bags具有特定的删除顺序。你可以想到Bag作为超类型Stack and Queue它通过特定的操作扩展了它的 api。

大多数时候，您只需要收集对象并以某种方式处理它们（迭代+元素处理）。所以你会用最简单的Bag这是一种单向链表的实现。