java - 在 Java 中使用 Bag 的原因

Question

我目前正在学习算法和数据结构，在阅读第 4 版算法书时，我发现了 Bag 数据结构以及 Stack和队列。在阅读了它的解释之后，我仍然不清楚为什么我更喜欢使用 Bag (没有 remove() 方法)而不是其他数据结构，例如作为 Stack、Queue、LinkedList 还是 Set？据我所知，Bag 的实现与 Stack 的实现相同，只是替换了 push()< 的名称 到 add() 并删除 pop() 方法。

所以 Bag 的想法基本上是能够收集元素，然后遍历收集到的元素，检查包是否为空，并找出其中元素的数量。但是在哪种情况下我最好使用 Bag 而不是上述集合之一？为什么 Bag 基本上没有 remove() 方法？有具体原因吗？

提前致谢。

Answer 1

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

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

LinkedList 是列表的实现，

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

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

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

示例:在 Java 中，LinkedList是一个集合，包，列表，队列，你也可以使用它作为一个堆栈，因为它支持堆栈操作(add~addLast~push, peekLast, removeLast~pop), 所以你也可以调用它堆栈。原因，为什么它不执行 Stack接口(interface)是，peek 方法由 Queue 保留检索列表头部(第一个元素)的实现。因此在 LinkedList 的情况下，“堆栈方法”派生自 Deque .

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

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

使用哪一种集合类型取决于您的需要，如果不需要重复，您可以使用 Set 而不是 Bag。此外，如果您关心移除顺序，您会选择 Stack 或 Queue，它们基​​本上是具有特定移除顺序的 Bags。您可以将 Bag 视为 Stack 和 Queue 的父类(super class)型，通过特定操作扩展其 api。

大多数时候，您只需要收集对象并以某种方式对其进行处理(迭代+元素处理)。因此，您将使用最简单的 Bag 实现，它是一个定向链表。