23种设计模式-行为型模式-迭代器

简介

迭代器是一种行为设计模式，让你能在不暴露集合底层表现形式(列表、栈和树等)的情况下遍历集合中所有的元素。

问题

集合是编程中最常使用的数据类型之一。 大部分集合使用简单列表存储元素。但有些集合还会使用栈、树、 图 和其他复杂的数据结构。
无论集合的构成方式是咋样的，它都必须提供某种访问元素的方式，便于 其他代码使用其中的元素。 集合应提供一种能够遍历元素的方式， 并且保证它不会重复地访问同一个元素。
如果你的集合基于列表， 遍历就会比较简单。但怎么遍历复杂数据结构(例如树)中的元素呢? 比如 今天你需要使用深度 优先算法来遍历树结构， 明天可能会需要广度优先算法; 下周则可能会需要其他方式(比如随机存取树中的元素)。 如下图。

这个时候，你可能不断往集合里添加遍历算法，这会让集合本身的职责（“高效存储数据” ）变得模糊，不符合单一职责原则。另外 有些算法可能是根据特定应用订制的， 把他加到泛型集合类中会 显得非常奇怪。
另一方面， 使用多种集合的客户端代码可能并不关心存储数据的方式，不过由于集合提供不同的元素访问方式， 你的代码就不得不跟特定集合类进行耦合。

解决

迭代器模式的主要思想是将集合的遍历行为抽取成单独的迭代器对象。

除实现自身算法外， 迭代器还封装了遍历操作的所有细节， 比如当前 位置和末尾剩余元素的数量。 因此，多个迭代器可以在相互独立的情况下同时访问集合。
迭代器通常会提供一个获取集合元素的基本方法。 客户端可以不断调用这个方法直到它不返回任何内容， 也就是说迭代器已经遍历了所有元素。
所有迭代器必须实现相同的接口。这样一来，只要有合适的迭代器，客户端代码就能兼容任何类型的集合或遍历算法。 如果你需要采用特殊方式来遍历集合， 只需创建一个新的迭代器类即可， 不需要对集合或客户端进行修改。

代码

// 1.Iterator接口 (定义遍历标准)
interface TreeIterator<T> {
    boolean hasNext();
    T next();
}

// 2.Concrete Iterator（实现广度优先遍历）
class BfsIterator implements TreeIterator<TreeNode> {
    private Queue<TreeNode> queue = new LinkedList<>();
    
    public BfsIterator(TreeNode root) {
        if(root != null) queue.add(root);
    }
    
    public boolean hasNext() {   // 判断是否有下一节点
        return !queue.isEmpty();
    }
    
    public TreeNode next() {     // 按层遍历树节点
        TreeNode current = queue.poll();
        for(TreeNode child : current.getChildren()) {
            queue.add(child);
        }
        return current;
    }
}

// 3.Collection接口（树结构抽象）
interface TreeCollection {
    TreeIterator<TreeNode> createBfsIterator(); // 创建特定迭代器
}

// 4.Concrete Collection（树节点实现）
class TreeNode implements TreeCollection {
    private String data;
    private List<TreeNode> children = new ArrayList<>();
    
    public TreeNode(String data) { 
        this.data = data; 
    }
    
    public void addChild(TreeNode node) {
        children.add(node);
    }
    
    public List<TreeNode> getChildren() { 
        return children; 
    }
    
    public TreeIterator<TreeNode> createBfsIterator() {
        return new BfsIterator(this); // 自身作为遍历起点
    }
}

// 5.Client使用示例
public class TreeClient {
    public static void main(String[] args) {
        /* 构建树结构：
           A
          / \
         B   C
            / \
           D   E
        */
        TreeNode root = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        root.addChild(nodeB);
        root.addChild(nodeC);
        nodeC.addChild(new TreeNode("D"));
        nodeC.addChild(new TreeNode("E"));
        
        // 获取BFS迭代器
        TreeIterator<TreeNode> iterator = root.createBfsIterator();
        
        // 遍历树节点
        while(iterator.hasNext()) {
            System.out.println(iterator.next().data); 
            // 依次输出 A → B → C → D → E
        }
    }
}

设计关键点：

1. 解耦遍历算法：BfsIterator封装广度优先的具体逻辑
2. 扩展性强：新增DfsIterator无需修改树结构代码
3. 多态迭代：客户端通过统一接口操作不同遍历方式

总结

1. (Iterator)接口声明了遍历集合所需的操作:获取下一个元素、 获取当前位置和重新开始迭代等。
2. (Concrete Iterators)实现遍历集合的一种特定算法。迭代器对象必须跟踪自身遍历的进度。这就让多个迭代器可以相互独立地遍历同一集合。
3. (Collection) 接口声明一个或多个方法来获取与集合兼容的迭代器。注意，方法返回的类型必须被声明成迭代器接口， 这样具体集合可以返回各种不同种类的迭代器。
4. (Concrete Collections)会在客户端请求迭代器时返回一个特定的具体迭代器类实体。
5. (Client) 通过集合和迭代器的接口来和这两者进行交互。 这样一来,客户端不需要跟具体类耦合，允许同一客户端代码使用各种不同的集合和迭代器。 客户端通常不会自行创建迭代器，而是会从集合里获取。但在特定情况下，客户端可以直接创建一个迭代器(比如当客户端需要自定义特殊迭代器时)。