数据结构中的包，其实是对现实中的包的一种抽象。 想像一下现实中的包，比如书包，它能做什么？有哪些功能？首先它用来装东西，里面的东西可以随便放，没有规律，没有顺序，当然，可以放多个相同的东西。其次，东西可以拿出来，拿出来也有几种情况，随便拿出一个，拿出特定的一个，比如书本，把所有的东西都拿出来。附带的功能就是，包有没有满，包是不是空的，里面有多少东西了，都是什么，里面是不是有书，放了几本书之类的。想好之后，就可以定义数据结构中的包的方法了。

　　装东西，定义add()方法，要接受一个参数，要装的东西，返回值呢？没有返回值。

　　随便拿出一个东西，定义remove()方法， 没有参数，返回拿出的东西。

　　拿出一个特定的东西，定义remove(anEntry), 接收一个参数，要拿出的东西，返回值是布尔值，表示有没有成功，因为要拿出的东西，包里可能没有

　　拿出所有东西，定义clear()方法，没有参数，也没有返回值。

　　包里有多少东西，定义getCurrentSize()方法，返回包中元素的个数，它没有参数，返回值是整数。

　　包是不是空的，定义isEmpty()方法，当然，它也没有参数，返回布尔值。

　　包里有没有书，定义contains()方法，它接受一个参数，要找的东西，返回布尔值。

　　包里有几本书，定义getFrequencyOf()方法，也是接受一个参数，返回的是整数。

　　包里都是什么，可以定义toArray()方法，返回一个数组，包含包里所有的东西，也是定义迭代方法。

/**
 * 一个用来描述包的操作的接口
 */
public interface BagInterface<T> {
    /**
     * 获取包中元素的数量
     *
     * @return 元素数量
     */
    int getCurrentSize();

    /**
     * 包是否为空
     *
     * @return 包为空，返回true, 否则返回false
     */
    boolean isEmpty();

    /**
     * 向包里添加一个元素
     *
     * @param newEntry 要添加到包里的元素
     */
    void add(T newEntry);

    /**
     * 从包里删除任意一个元素
     * @return 删除的元素
     */
    T remove();

    /**
     * 从包里删除一个给定的元素
     * @param anEntry 要删除的元素
     * @return 是否删除成功
     */
    boolean remove(T anEntry);

    /**
     * 删除包中所有元素
     */
    public void clear();

    /**
     * 计算一个给定元素的数量
     * @param anEntry 给定的元素
     * @return 给定元素的数量
     */
    public int getFrequencyOf(T anEntry);

    /**
     * 是否包含给定的元素
     * @param anEntry 要查找的元素
     * @return 如查包含返回true, 否则返回false
     */
    public boolean contains(T anEntry);

    /**
     * 获取包中所有的元素，
     * @return 包含包中所有元素新数组。
     * 注意，如果包为空，返回空数组
     */

    T[] toArray();
}

　　使用数组实现Bag --- 创建ArrayBag类来实现BagInterface

　　在实现方法之前，先考虑一下类的属性。由于包(bag)是用来存储东西的，所以一个属性是数组，用来存储元素。包有容量，数组有长度，还要决定数组的长度。既也可以让使用者来决定，也可以提供一个默认容量。除此之外，还要记录包中元素的个数

private T[] bag;
private int numberOfEntries;
private static final int DEFAULT_CAPACITY = 25;

　　构造方法，初始化包。首先是创建数组对象，赋值给bag属性，因为属性中的bag只是一个数组的引用，并没有真正地创建数组。其次，由于创建的是空数组，numberOfEntries初始化为0. 但怎么创建数组呢？假设构造函数接收一个参数capacity,  bag = new T[capacity]; 不行。bag = new Object[capacity]; 还是不行。bag = (T[])new Object[capacity]; 倒是没有报错，但有warning(unchecked cast). 编译器想让你确保数组中的每一个元素从Object类强制转化成泛型T是安全的，由于数组刚刚创建，每一个元素都是null，因此转化是安全的，我们可以使用@SuppressWarnings("unchecked")告诉编译器忽略这个warning。@SuppressWarnings("unchecked")只能出现在方法定义或变量声明之前，由于bag = (T[])new Object[capacity]; 是赋值操作，不是变量声明，因为bag已经声明了，还要转化成

// 强制类型转化是安全的，因为新数组中所有元素都是null
@SuppressWarnings("unchecked")
T[] tempBag = (T[])new Object[capacity]; // Unchecked cast
bag = tempBag;

　　整个构造函数如下

    /**
     * 创建一个空bag，初始空量为用户指定容量
     * @param capacity 指定容量
     */
    public ArrayBag(int capacity) {
        // 强制类型转化是安全的，因为新数组中所有元素都是null
        @SuppressWarnings("unchecked")
        T[] tempBag = (T[]) new Object[capacity]; // Unchecked cast
        bag = tempBag;
        numberOfEntries = 0;
    }

    /**
     * 创建一个空bag，初始空量为默认容量25
     */
    public ArrayBag() {
        this(DEFAULT_CAPACITY);
    }

　　添加方法add，如果数组满了，就不能添加了，需要扩容，如果数组没有满，就可以继续添加。扩容后面再说，先看添加。添加元素，就是把要添加的元素直接放到数组中最后一个元素的后面，元素个数加1。刚开始时，数组为空，numberOfEntries为0，数组中没有元素，直接在0位置放置新元素，然后numberOfEntries + 1。再添加一个元素，那就要放到1的位置，numberOfEntries+1。再添加一个元素，那就要放到2的位置，numberOfEntries+1。

　　你会发现，新元素的放置位置就是bag[numberOfEntries]的位置，add()方法就是

public void add(T newEntry) {
    if(isArrayFull()){

    } else {
      bag[numberOfEntries] = newEntry;
      numberOfEntries++;
    }
}

　　实现isArrayFull很简单，元素的个数等于数组的长度就满了。

private boolean isArrayFull() {
    return numberOfEntries == bag.length;
}

　　ToArray() 方法，也比较好实现，创建一个新数组，把bag中的元素复制过去

public T[] toArray() {
    @SuppressWarnings("unchecked")
    T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
    for (int index = 0; index < numberOfEntries; index++)
    {
        result[index] = bag[index];
    } // end for
    return result;
}

 　　现在可以向bag中添加元素，也可以查看bag中的元素，是时候实现其它方法了。先从简单的开始，isEmpty(),  getCurrentSize(), 

public boolean isEmpty() {
    return numberOfEntries == 0;
}
public int getCurrentSize() {
    return numberOfEntries;
}

　　 getFrequencyOf()，计算一个元素在bag中出现的次数，就是计算一个元素在数组中出现的次数。使用for循环，遍历数组中的每一个元素，只要有元素和要查找的元素相等，计数器加1。遍历完成后，返回计数器，就可以了。

public int getFrequencyOf(T anEntry) {
    int count = 0;

    for (int i = 0; i < numberOfEntries; i++) {
        if(anEntry.equals(bag[i])){
            count++;
        }
    }
    return count;
}

　　contains()方法，bag中是否包含某一个元素，还是循环遍历数组，只不过返回的true或false，在遍历中，只要有一个元素和要查找的元素相等，那就返回true。可以先设一个表示找到找不到的变量found,默认是false，只有当fasle的时候，才遍历数组，在遍历过程中，如果找到了，设为true。

public boolean contains(T anEntry) {
    boolean found = false;
    int index = 0;
    
    while (!found && index < numberOfEntries){
        if (anEntry.equals(bag[index])){
            found = true;
        }
        
        index++;
    }
    return found;
}

　　clear()方法，清空bag，简单一点的实现，就是numberOfEntries = 0;，复杂一点就是bag不为空的时候，循环调用remove()方法

public void clear() {
    // numberOfEntries = 0;
    while (!isEmpty()){
        remove();
    }
}

　　remove() 方法，删除任意一个元素，由于bag中的元素是没有顺序和规律的，可以随便删除，简单起见，我们就删除最后一个元素，当然，如果bag为空的话，删除是要报错的。

public T remove() {
    if (isEmpty()) {
        throw new RuntimeException("空");
    }
    
    T result = bag[numberOfEntries - 1];
    bag[numberOfEntries - 1] = null;
    numberOfEntries--;
    
    return result;
}

　　remove(anEntry)，删除一个给定的元素，首先要先查找这个元素，如果bag中没有这个元素，也就没有办法删除，直接return false就好了。如果找到了，再想办法删除。查找，用的是循环遍历，找到了，也就是找到了这个元素所在的位置。

　　怎么删除呢？最先想到的是把后面的元素向前移，因为数组是连续的。

 

　　有点复杂了。因为bag中的元素，并没有规定顺序，也就没有必要前移。我们可以让要删除的元素和最后一个元素，进行交换，直接删除最后一个元素就好了。

 

public boolean remove(T anEntry) {
    if(isEmpty()){
        throw new RuntimeException("空");
    }

    boolean found = false;
    int index = 0;
    while (!found && index < numberOfEntries){
        if (anEntry.equals(bag[index])){
            found = true;
        } else {
            index++;
        }
    }

    if(found){
        bag[index] = bag[numberOfEntries - 1];
        bag[numberOfEntries - 1] = null;
        numberOfEntries--;
        return true;
    } else {
        return false;
    }
}