算法1.4 背包(FIFO)

算法1.4 背包(Bag)

import java.util.Iterator;
public class Bag<Item> implements Iterable<Item>{
    private class Node{
        Item item;
        Node next;
    }
    private Node first;
    private int N;
    public boolean isEmpty(){ return N == 0; }
    public int size(){ return N; }
    public void add(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }//和Stack的push()相同
    @Override
    public Iterator<Item> iterator(){
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item>{
        private Node current = first;
        @Override
        public boolean hasNext(){ return current != null;}
        @Override
        public Item next(){
            Item item = current.item;
            current = current.next;
            return item;
        }
        @Override
        public void remove(){}
    }
}

要点

1. 背包也是FIFO策略,即一个没有pop()的Stack,将push()改名为add();

特点

1. 可以处理任何类型的数据
2. 所需空间和集合大小成正比
3. 操作所需时间和集合大小无关