当前位置：首页 > 文章列表 > 文章 > java教程 > 理解Java中的Bag ADT：一种灵活的数据结构

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

来源：dev.to 2024-12-31 21:42:59 0浏览收藏

从现在开始，我们要努力学习啦！今天我给大家带来《理解Java中的Bag ADT：一种灵活的数据结构》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

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

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

图1
可更新集合
理解Java中的Bag ADT：一种灵活的数据结构
注意：链接缓冲区是 updatablebag 的实现，由任意数量的保存元素的缓冲区组成，排列在列表中。每个缓冲区保存一个元素数组。 arbtree 是 updatablebag 的实现，elementsortedcollection 实现红黑树，一种平衡排序二叉搜索树的形式。摘自 lee (n. d.) 的收藏包概述。

bag 的属性可以定义如下：

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

图2
包类 uml
理解Java中的Bag ADT：一种灵活的数据结构
注意：来自 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）

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: 50
Apples after selling 2: 48

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

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