在Java中使用Bag的原因 [英] Reasons for using a Bag in Java

问题描述

我目前正在研究算法和数据结构，当我阅读《算法之书》第四版时，我发现了 Bag 数据结构以及 Stack 和队列。
在阅读了解释之后，我仍然不清楚使用 Bag （没有 remove（ ）方法），例如 Stack ， Queue ， LinkedList 或 Set ？
据我从书中了解到， Bag 的实现与 Stack ，只需将 push（）的名称替换为 add（），然后删除 pop（）方法。

I am currently studying about Algorithms & Data Structures and while I was reading over the Book of Algorithms 4th edition, I discovered the Bag data-structure together with the Stack and Queue. After reading the the explanation of it, it is still unclear to me what would I prefer using a Bag (which has no remove() method) over other data-structures such as Stack, Queue, LinkedList or a Set? As far as I can understand from the Book, the implementation of a Bag, is the same as for a Stack, just replacing the name of push() to add() and remove the pop() method.

所以 Bag 的想法基本上是具有收集物品的能力，然后遍历收集到的物品，检查袋子是否为空并找到其中的物品数量。
但是在哪种情况下，我最好在上述集合之一中使用 Bag ？为什么 Bag 基本上没有 remove（）方法？

So the idea of a Bag is basically having the ability to collect items and then iterate through the collected items, check if a bag is empty and find the number of items in it. But under which circumstances I would better using a Bag over one of the mentioned above Collections? And why a Bag doesn't have a remove() method basically? is there a specific reason for it?

预先感谢。

推荐答案

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

Stack is ADT of the collection of elements with specific remove order = LIFO (last-in-first-out), allows duplicates,

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

Queue is ADT of the collection of elements with specific remove order = FIFO (first-in-first-out), allows duplicates,

LinkedList 是列表的实现，

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

Set is ADT of the collection of elements which disallows duplicates,

Bag

Bag is ADT of the collection of elements which allows duplicates.

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

In general, anything that holds an elements is Collection. Any collection which allows duplicates is Bag, otherwise it is Set. Any bag which access elements via index is List. Bag which appends new element after the last one and has a method to remove element from the head (first index) is Queue. Bag which appends new element after the last one and has a method to remove element from the tail (last index) is Stack.

示例：在Java中， LinkedList 是一个集合，包，列表，队列，您也可以使用它，因为它是堆栈，因为它支持堆栈操作（ add 〜 addLast 〜 push ， peekLast ， removeLast 〜 pop ），因此您也可以将其称为堆栈。之所以不能实现堆栈界面是，peek 方法.html rel = noreferrer>队列实现，该实现检索列表的开头（第一个元素）。因此，在 LinkedList 的情况下，堆栈方法源自 Deque 。

Example: In Java, LinkedList is a collection, bag, list, queue and also you can work with it as it was a stack since it support stack operations (add~addLast~push, peekLast, removeLast~pop), so you can call it also stack. The reason, why it does not implement Stack interface is, that peek method is reserved by Queue implementation which retrieves the head of the list (first element). Therefore in case of LinkedList, the "stack methods" are derived from Deque.

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

Whether Bag contains remove(Object) or not may depend on the implementation e. g. you can implement your own Bag type which supports this operation. Also you can implement get(int) operation to access object on specified index. Time complexity of the get(int) would depend on your implementation e. g. one can implement Bag via linked-list so the complexity would be at average O(n/2), other one via resizable array (array-list) with direct access to the element via index, so the complexity would be O(1).

但是 Bag 的主要思想是，它允许重复和遍历此集合。它是否支持其他有用的操作取决于实现者的设计决定。

But the main idea of the Bag is, that it allows duplicates and iteration through this collection. Whether it supports another useful operations depends on implementator's design decision.

要使用哪种收集类型取决于您的需求，如果不需要重复，则可以使用 Set ，而不是 Bag 。此外，如果您关心删除订单，则可以选择 Stack 或 Queue ，它们基​​本上是 Bags （带有特定的删除顺序）。您可以将 Bag 视为 Stack 和 Queue 会通过特定操作扩展其api。

Which one of the collection type to use dependes on your needs, if duplicates are not desired, you would use Set instead of Bag. Moreover, if you care about remove order you would pick Stack or Queue which are basically Bags with specific remove order. You can think of Bag as super-type of the Stack and Queue which extends its api by specific operations.

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

Most of the time, you just need to collect objects and process them in some way (iteration + element processing). So you will use the most simple Bag implementation which is one directional linked-list.

这篇关于在Java中使用Bag的原因的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！