背包

Author Avatar
Brian Lee 7月 27, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:背包

目的

帮助用例收集元素并迭代遍历所有收集到的元素。用例也可以检查背包是否为空或者获取背包中元素的数量。

特点

  • 迭代的顺序不确定且与用例无关
  • 不支持从中删除元素

API

public class Bag<Item> implements Iterable<Item>

Bag() 创建一个空背包
void add(Item item) 添加一个元素
boolean isEmpty() 背包是否为空
int size() 背包中的元素数量

实现

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 ++;
    }
    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;
        }
    }
}

源码地址

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S1_foundation/S1_3_BagQueueStack/S1_3_3_10_Bag

本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/07/27/Bag/