在Java中使用Bag的原因

Question

我目前正在研究算法和数据结构,当我阅读Book of Algorithms第4版时,我发现了Bag数据结构以及Stack和Queue.读它的解释后,仍然不清楚我,我会更喜欢使用什么Bag(它没有remove()比其他的数据结构,如法)Stack,Queue,LinkedList还是Set？据我所知,本书的实现与a Bag相同Stack,只是替换了push()to 的名称add()并删除了该pop()方法.

所以a的想法Bag基本上是能够收集物品然后遍历收集的物品,检查行李是否为空并找到其中的物品数量.但在哪种情况下我会更好地使用Bag上面提到的一个以上的集合？为什么一个基本上Bag没有remove()方法？它有特定的原因吗？

提前致谢.

Answer 1

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

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

LinkedList 是列表的实现,

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

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

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

例如:在Java中,LinkedList的是一个集合,包,表,队列,你也可以使用它,因为它是一个堆栈,因为它支持堆栈操作(add〜addLast〜push,peekLast,removeLast〜pop),所以你可以把它也叠加.原因,为什么它没有实现Stack接口,该peek方法由Queue实现保留,它检索列表的头部(第一个元素).因此,在LinkedList的情况下,"堆栈方法"是从Deque派生的.

是否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实现,即单向链接列表.