概念

背包是一种不支持从中删除元素的集合数据类型 —— 它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素。所以使用 Bag 的 API，用 add 收集元素和用 foreach 遍历所有收集的元素 。

那么背包这种数据结构与堆栈、队列有何区别呢。若使用背包，那么说明元素处理的顺序不重要。所以背包的经典场景，就是收集数据后求平均值。

基于链表实现背包

用链表实现 Bag 只需将 Stack 中的 push() 改为 add()，并去掉 pop() 的实现即可。虽然正好也是后进先出的顺序，但顺序在这里并不重要。

public class Bag<Item> implements Iterable<Item> {
    private Node first;    // 链表的首结点

    private class Node{
        private Item item;
        private Node next;
    }

    public void add(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public Iterator<Item> iterator()  {
        return new ListIterator();  
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext()  { return current != null; }
        public void remove()      {  }

        public Item next() {
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }

    public static void main(String[] args) {
        Bag<String> bag = new Bag<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            bag.add(item);   // 收集
        }
        for (String s : bag) {   // 遍历
            StdOut.println(s);
        }
    }
}

运行结果：