理解Java中的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;   }  } } 

/**  * 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