理解Java中的Bag ADT：一种灵活的数据结构

本文介绍了 java 中的 bag 抽象数据类型 (adt)，重点介绍了它处理具有重复元素和动态调整大小的无序集合的能力。通过详细的实现示例，它演示了 bag adt 如何提供有效的解决方案来管理库存系统等实际应用程序中的集合。

在计算机科学中，抽象数据类型（adt）对于管理和组织数据至关重要。它们可以被定义为“描述数据集以及对该数据的操作的规范”（carrano & henry，2018）。在java中，adt广泛用于包、栈、队列、集合等集合的开发。本文重点介绍 bag adt，它允许重复元素、支持动态调整大小并提供处理无序集合的灵活性。 java 中的 bag 类型是属于 collection 类的基本数据类型，见图 1。

图1
可更新集合

注意：链接缓冲区是 updatablebag 的实现，由任意数量的保存元素的缓冲区组成，排列在列表中。每个缓冲区保存一个元素数组。 arbtree 是 updatablebag 的实现，elementsortedcollection 实现红黑树，一种平衡排序二叉搜索树的形式。摘自 lee (n. d.) 的收藏包概述。

bag 的属性可以定义如下：

重复 — 允许重复。无序 — bag 元素未排序。动态调整大小 — 大小可以动态更改。可迭代——在 java 中，包是可以迭代的。无索引 — 包元素未建立索引。高效的添加操作 – 将元素添加到包中通常是 o(1) 操作。支持集合操作。见图2。通用类型——包可以容纳任何类型的元素。没有键值对 — 包存储没有关联键的元素。可变 — 包的内容在创建后可以更改，可以动态调整大小。支持空元素 – 包可能允许空元素。

图2
包类 uml

注意：来自 carrano 和 henry 的《data structures and abstractions with java》（第五版）（2018 年）。

在 java 编程语言的上下文中，堆栈、队列、

linkedlist、set 和 bag 可以描述如下：堆栈是具有特定删除顺序的元素集合的adt = lifo（后进先出），允许重复。队列是具有特定移除顺序的元素集合的adt = fifo（先进先出），允许重复。linkedlist 是列表的实现。set 是元素集合的 adt，不允许重复。bag是允许重复的元素集合的adt。

换句话说，任何包含元素的集合都是collection，任何允许重复的集合都是bag，否则就是set。 （马托尼，2017）

立即学习“Java免费学习笔记（深入）”；

bag 的主要好处是它允许重复和迭代，它也是可变的，允许动态调整其元素的大小和修改。换句话说，“如果不需要重复项，您可以使用 set 而不是 bag。此外，如果您关心删除顺序，您会选择堆栈或队列，它们基本上是具有特定删除顺序的包。您可以将 bag 视为 stack 和 queue 的超类型，它通过特定操作扩展其 api”（matoni，2017）。下面的程序是 bag adt 方法对杂货库存的简单实现的示例。

bag 类实现 bag adt

import java.util.iterator;import java.util.nosuchelementexception;/** * a simple implementation of a bag adt (abstract data type). it implements a * linked structure systems, a chain data structure. [item | next] -> [item | * next] -> [item | next] -> null. *  * @param  the type of elements held in this bag * * @author alejandro ricciardi * @date 08/12/2024 */public class bag implements iterable { private node headnode; // the first node in the bag list private int size; // number of node in the bag /**  * private inner class that creates a node in the linked structure. each node  * contains an item and a reference to the next node. [item | next] -> [item |  * next] -> [item | next] -> null  *   */ private class node {  t item; // the item stored in the node  node next; // reference to the next node } /**  * constructs an empty bag.  */ public bag() {  headnode = null; // initialize the first (head) node in the bag to null                                 (empty bag)  size = 0; // initialize size of the bag to 0 } /**  * adds the specified item to this bag. this operation runs in constant time  * o(1).  *  * @param item the item to add to the bag  */ public void add(t item) {  node nextnode = headnode; // save the current head node becoming the next                                     // node in the added node  headnode = new node(); // create a new node and make it the head node  headnode.item = item; // set the item of the new node  headnode.next = nextnode; // link the new node to the old head node  size++; // increment the size of the bag } /**  * removes one item from the bag if it exists. this operation runs in linear  * time o(n) in the worst case.  *  * @param item the item to remove  * @return true if the item was found and removed, false otherwise  */ public boolean remove(t item) {  if (headnode == null)   return false; // if the bag is empty, return false  if (headnode.item.equals(item)) { // if the item is in the first node   headnode = headnode.next; // make the next node the new head node   size--; // decrement the size   return true;  }  node current = headnode;  while (current.next != null) { // iterates the linked structure   if (current.next.item.equals(item)) { // if the next node contains                                                        // the item    current.next = current.next.next; // remove the next node from                                                        // the chain    size--; // decrement the size    return true;   }   current = current.next; // move to the next node  }  return false; // item not found in the bag } /**  * returns the number of items in this bag.  *  * @return the number of items in this bag  */ public int size() {  return size; } /**  * checks if this bag is empty.  *  * @return true if this bag contains no items, false otherwise  */ public boolean isempty() {  return size == 0; } /**  * returns an iterator that iterates over the items in this bag.  *  * @return an iterator that iterates over the items in this bag  */ public iterator iterator() {  return new bagiterator(); } /**  * private inner class that implements the iterator interface.  */ private class bagiterator implements iterator {  private node current = headnode; // start from the first (head) node  /**   * checks if there are more elements to iterate over.   *   * @return true if there are more elements, false otherwise   */  public boolean hasnext() {   return current != null;  }  /**   * returns the next element in the iteration.   *   * @return the next element in the iteration   * @throws nosuchelementexception if there are no more elements   */  public t next() {   if (!hasnext())    throw new nosuchelementexception();   t item = current.item; // get the item from the current node   current = current.next; // move to the next node   return item;  } }}

登录后复制

groceryinventory 使用 bag adt 方法实现了一个简单的杂货店库存管理系统：

/** * a simple grocery store inventory management system using a bag adt. *  * @author alejandro ricciardi * @date 08/12/2024  */public class groceryinventory {    // the bag adt used to store items    private bag inventory;    /**     * constructs a new grocoryinventory      */    public groceryinventory() {        inventory = new bag();    }    /**     * adds items to the inventory.     *      * @param item the name of the item to add.     * @param quantity the number of items to add.     */    public void addshipment(string item, int quantity) {        // add the item to the bag 'quantity' times        for (int i = 0; i < quantity; i++) {            inventory.add(item);        }    }    /**     * removes item from the inventory.     *      * @param item the name of the item to remove.     * @return true if the item was successfully removed, false otherwise.     */    public boolean sellitem(string item) {        return inventory.remove(item);    }    /**     * counts the number of a specific item in the inventory (duplicates).     *      * @param item the name of the item to be counted.     * @return the number of this item in the inventory.     */    public int getitemcount(string item) {        int count = 0;        // iterate through the bag and count the number of the given item in it        for (string s : inventory) {            if (s.equals(item)) {                count++;            }        }        return count;    }    /**     * main method.     */    public static void main(string[] args) {        groceryinventory store = new groceryinventory();        // add inventory        store.addshipment("apple", 50);        store.addshipment("banana", 30);        store.addshipment("orange", 40);        // initial apple count        system.out.println("apples in stock: " + store.getitemcount("apple"));        // selling apples        store.sellitem("apple");        store.sellitem("apple");        // apple count after selling        system.out.println("apples after selling 2: " +                             store.getitemcount("apple"));    }}

登录后复制

输出

Apples in stock: 50Apples after selling 2: 48

登录后复制

bag adt 在这个例子中很有用，因为它是可迭代的，它可以存储同一对象的多个实例（例如，像苹果这样的重复项），并创建一个抽象来简化对项目数据的操作，并且不需要项目待订购。与数组不同，bag 不需要固定大小，可以根据需要动态调整大小。此外，它们（对于本示例）比列表更好，因为它们不需要订购物品（例如，苹果可以存储在香蕉之后或之前）。此外，它们比 sets 更好（对于本例），因为它们允许重复（例如，您可以在商店里拥有多个苹果）。

换句话说，在这个例子中很有用并且更好，因为：

您可以轻松添加多个苹果或香蕉 (addshipment)。您可以在单个商品售出后将其移除 (sellitem)。您可以计算您拥有的每件物品的数量 (getitemcount)

总之，java 中的 bag adt 是一种灵活且高效的管理元素集合的方法，特别是在需要重复和动态调整大小时。它是一个简单但功能强大的结构，允许轻松添加、删除和迭代元素，使其成为库存系统等应用程序的理想选择，如杂货店示例所示。

参考文献：

carrano, f.m. 和 henry, t.m.（2018 年，1 月 31 日）。 java 的数据结构和抽象（第五版）。皮尔逊。

lee, d. (n. d.)。收藏包概述 [doug lea 的主页]。纽约州立大学计算机科学系。 https://gee.cs.oswego.edu/dl/classes/collections/

马托尼（2017 年，4 月 15 日）。在 java 中使用 bag 的原因 [post]。堆栈溢出。 https://stackoverflow.com/questions/43428114/reasons-for-using-a-bag-in-java

最初于 2024 年 10 月 3 日发表于 alex.omegapy – medium。

以上就是理解Java中的Bag ADT：一种灵活的数据结构的详细内容，更多请关注【创想鸟】其它相关文章！