ARTICLE DETAIL

资讯详情

深耕郑州网站建设与运营推广的一线实战洞察。

Java 迭代器模式(Iterator Pattern)实战解析:从 Treasure Chest 到 BST 中序遍历

Java 迭代器模式(Iterator Pattern)实战解析:从 Treasure Chest 到 BST 中序遍历 示例工程教程【免费下载链接】java-design-patternsDesign patterns implemented in Java项目地址https://gitcode.com/GitHub_Trending/ja/java-design-patterns点击查看免费下载本篇技术指南以 iterator 模块 为核心系统讲解 Gang of Four 行为型设计模式之一的迭代器模式Iterator Pattern又名 Cursor 游标。该模式在不暴露集合底层表示的前提下为顺序访问聚合对象元素提供统一入口。结合本仓库中的TreasureChest宝藏箱过滤迭代器与BstIterator二叉搜索树中序遍历迭代器两份完整实现你将掌握迭代器接口设计、过滤遍历原理、O(h) 空间复杂度的树形结构迭代以及如何通过测试验证迭代行为。Iterator 模式类图 工厂方法创建 TreasureChestItemIterator 迭代器)Iterator 模式时序图模式定位解决什么问题迭代器模式属于行为型Behavioral设计模式其核心目的是提供一种顺序访问聚合对象元素的方法而无需暴露其底层表示underlying representation。简而言之容器可以为访问者提供一种与自身内部存储结构无关的迭代接口。客户端只依赖hasNext()与next()两个抽象操作完全不关心元素究竟是存放在数组、链表、还是树中——这正是解耦算法与容器的体现本模块 App.java 的类注释也明确写道The Iterator pattern decouples algorithms from containers迭代器模式将算法与容器解耦。一个直观的现实类比宝藏箱Treasure Chest中存放着多种魔法物品戒指、药水、武器。游客不需要知道箱子内部如何堆放只需借助一个按类型检索的迭代器就能逐个取出指定类型的物品。从维基百科的定义看在面向对象编程中迭代器模式使用一个迭代器对象来遍历容器并访问容器中的元素。Java 语言本身已将其内建为java.util.Iterator与更古老的java.util.Enumeration接口本模块则是从零实现这一思想的教科书级示例。程序示例宝藏箱按类型迭代聚合对象 TreasureChestTreasureChest.java 是模式中的Aggregate聚合对象内部持有一个不可变的ListItem构造时初始化 10 件魔法物品public class TreasureChest { private final ListItem items; public TreasureChest() { items List.of( new Item(ItemType.POTION, Potion of courage), new Item(ItemType.RING, Ring of shadows), new Item(ItemType.POTION, Potion of wisdom), new Item(ItemType.POTION, Potion of blood), new Item(ItemType.WEAPON, Sword of silver 1), new Item(ItemType.POTION, Potion of rust), new Item(ItemType.POTION, Potion of healing), new Item(ItemType.RING, Ring of armor), new Item(ItemType.WEAPON, Steel halberd), new Item(ItemType.WEAPON, Dagger of poison)); } public IteratorItem iterator(ItemType itemType) { return new TreasureChestItemIterator(this, itemType); } public ListItem getItems() { return new ArrayList(items); } }两个关键设计细节值得注意iterator(ItemType itemType)是工厂方法客户端通过它获取针对特定物品类型的迭代器而不必直接实例化迭代器实现类getItems()返回new ArrayList(items)即防御性拷贝避免调用方直接修改聚合对象内部状态保护了封装性。元素 Item 与枚举 ItemTypeItem.java 使用 Lombok 简化样板代码type字段可读写name字段只读toString()直接返回物品名称AllArgsConstructor public class Item { Getter Setter private ItemType type; private final String name; Override public String toString() { return name; } }物品类型由枚举ItemType定义共四个取值public enum ItemType { ANY, WEAPON, RING, POTION }其中ANY是通配类型表示不过滤任何类型、遍历全部物品。极简的迭代器抽象本模块自定义的 Iterator.java 泛型接口只有两个方法这是整个模式的契约核心public interface IteratorT { boolean hasNext(); T next(); }hasNext()询问是否还有下一个元素供客户端在循环中作为守卫条件next()返回下一个元素并推进游标。这一契约与 Java 标准库java.util.Iterator的语义一致但剥离了可选的remove()等扩展方法只保留最小必要接口更便于理解模式本质。源码深挖过滤迭代器的实现原理模式的灵魂在于 TreasureChestItemIterator.java。它持有聚合对象引用、游标idx和过滤类型type每次调用next()时通过findNextIdx()线性扫描底层列表跳过不匹配类型的元素public class TreasureChestItemIterator implements IteratorItem { private final TreasureChest chest; private int idx; private final ItemType type; public TreasureChestItemIterator(TreasureChest chest, ItemType type) { this.chest chest; this.type type; this.idx -1; } Override public boolean hasNext() { return findNextIdx() ! -1; } Override public Item next() { idx findNextIdx(); if (idx ! -1) { return chest.getItems().get(idx); } return null; } private int findNextIdx() { var items chest.getItems(); var tempIdx idx; while (true) { tempIdx; if (tempIdx items.size()) { tempIdx -1; break; } if (type.equals(ItemType.ANY) || items.get(tempIdx).getType().equals(type)) { break; } } return tempIdx; } }从实现可以总结出几个关键点游标语义idx初始为-1表示尚未开始遍历findNextIdx()在临时变量tempIdx上推进找到匹配元素后才回写idx保证hasNext()的查询不会污染当前游标位置惰性扫描hasNext()与next()都依赖findNextIdx()现场查找而不是在构造时预先过滤出结果列表——这是典型的惰性迭代lazy iteration元素是按需定位的终止条件当tempIdx越过列表末尾时置为-1hasNext()据此返回falseANY 通配type.equals(ItemType.ANY)时跳过类型比较直接放行所有元素防御性拷贝的代价每次findNextIdx()都调用chest.getItems()生成新 ArrayList实现上保证了外部无法篡改代价是多次拷贝的少量开销仅用于教学演示场景。从源码结构看这里体现的是过滤型迭代器的通用思路迭代器内部自行维护遍历状态与筛选逻辑对客户端完全透明。使用方式客户端遍历循环在 App.java 中遍历通过标准的while (iterator.hasNext())循环完成private static void demonstrateTreasureChestIteratorForType(ItemType itemType) { LOGGER.info(------------------------); LOGGER.info(Item Iterator for ItemType itemType : ); var itemIterator TREASURE_CHEST.iterator(itemType); while (itemIterator.hasNext()) { LOGGER.info(itemIterator.next().toString()); } }主入口依次演示了 RING、POTION、WEAPON、ANY 四种类型的遍历。以 RING 为例程序输出Ring of shadows Ring of armor与宝藏箱中仅有的两件戒指物品一一对应。遍历其他类型的完整输出规律如下POTIONPotion of courage、Potion of wisdom、Potion of blood、Potion of rust、Potion of healing共 5 件WEAPONSword of silver 1、Steel halberd、Dagger of poison共 3 件ANY全部 10 件物品按原顺序依次输出。进阶实现BST 中序遍历迭代器迭代器模式的价值在于同一套接口适用于截然不同的数据结构。本模块的 bst 子包展示了针对二叉搜索树BST的实现——BstIterator.java 实现的是中序遍历in-order traversal即按元素自然顺序1、2、3…输出public class BstIteratorT extends ComparableT implements IteratorTreeNodeT { private final ArrayDequeTreeNodeT pathStack; public BstIterator(TreeNodeT root) { pathStack new ArrayDeque(); pushPathToNextSmallest(root); } private void pushPathToNextSmallest(TreeNodeT node) { while (node ! null) { pathStack.push(node); node node.getLeft(); } } Override public boolean hasNext() { return !pathStack.isEmpty(); } Override public TreeNodeT next() throws NoSuchElementException { if (pathStack.isEmpty()) { throw new NoSuchElementException(); } var next pathStack.pop(); pushPathToNextSmallest(next.getRight()); return next; } }该实现有三个值得学习的设计点显式栈 惰性推进与递归中序遍历不同这里使用ArrayDeque作为栈保存待访问节点。构造时pushPathToNextSmallest(root)将根到最左叶子路径上的所有节点压栈next()弹出栈顶节点后再对其右子树重复压栈——这保证了整个迭代过程只使用 O(h) 额外空间h 为树高且每次next()平均 O(1)比一次性生成完整中序列表更节省空间与 List 迭代器行为一致hasNext()通过栈是否为空判断空树root 为 null时栈为空next()抛出NoSuchElementException语义与 Java 标准迭代器完全对齐泛型约束T extends ComparableT保证节点值可比较从而确保中序 自然顺序。配合 TreeNode.java 提供的insert()插入逻辑App中构造了一棵根为 8、依次插入 3、10、1、6、14、4、7、13 的 BST遍历输出为Next node: 1 Next node: 3 Next node: 4 Next node: 6 Next node: 7 Next node: 8 Next node: 10 Next node: 13 Next node: 14正是二叉搜索树的中序序列升序排列直观验证了迭代器与数据结构之间的完全解耦客户端只认识hasNext()/next()而对栈 树的内部机制一无所知。测试验证迭代行为如何被守护模块的测试用例从契约层面验证了迭代器的正确性TreasureChestTest.java通过参数化测试ParameterizedTestMethodSource枚举宝箱中的全部 10 件物品逐件验证TreasureChestItemIterator能将其检索出来同时校验next()返回非空BstIteratorTest.java覆盖两类场景——非空树按升序返回全部节点、hasNext()在遍历完毕后返回false对空树调用next()则断言抛出NoSuchElementException与 BstIterator.java 的异常路径对应AppTest.java验证程序入口可正常启动运行。这些测试共同守护了迭代器协议的三条铁律遍历完整、顺序正确、越界有明确失败语义。适用场景与设计取舍根据 localization/es/iterator/README.md 及源码实现迭代器模式适用于以下场景需要在不暴露内部表示的前提下访问聚合对象内容——客户端只面对Iterator接口聚合结构List、树、Set 等可以随时替换而不影响调用方需要支持对同一聚合对象的多种遍历方式——例如宝箱按类型过滤、按原始顺序遍历BST 按中序/前序/后序遍历每种遍历对应一个独立迭代器需要为不同类型的聚合结构提供统一的遍历接口——无论 List 还是树客户端代码形态完全一致提升复用性与可扩展性。优点降低耦合数据结构与遍历算法彻底分离算法不再依赖容器的具体形态统一接口不同数据结构的遍历方式对外完全一致便于编写通用处理逻辑职责单一遍历状态游标、栈由迭代器自持聚合对象保持简洁。权衡对象开销相比直接索引访问迭代器对象的创建与调用存在少量性能开销本模块的防御性拷贝过滤实现尤甚对超高性能敏感路径需评估复杂结构的迭代器复杂度树、图等复杂聚合的中序/层序等迭代器实现与维护成本较高边界条件空结构、遍历中断后恢复需要仔细处理。与相关模式的关系Composite组合模式迭代器常用于遍历组合树形结构中的节点Factory Method工厂方法TreasureChest.iterator()正是工厂方法思想的体现——为不同数据结构创建各自合适的迭代器Visitor访问者模式可与迭代器配合在遍历元素的同时对其施加各种操作实现遍历 分派的组合。快速上手在仓库根目录下执行 Maven 命令即可运行本模块示例并执行测试./mvnw -pl iterator compile exec:java # 运行 App 演示 ./mvnw -pl iterator test # 运行全部迭代器测试以 pom.xml 与根目录 mvnw 为准若本机已安装 Maven可直接使用mvn。通过本模块的两个实现List 过滤迭代器与 BST 中序遍历迭代器可以清晰地看到迭代器模式用最小的接口契约换来了聚合结构与遍历算法之间最大程度的松耦合——这正是它在 Java 集合框架乃至各类数据处理库中被广泛内建使用的根本原因。若需继续深入可对照 英文版模块 README 与 西班牙语版文档 交叉阅读。赞分享示例工程教程【免费下载链接】java-design-patternsDesign patterns implemented in Java项目地址https://gitcode.com/GitHub_Trending/ja/java-design-patterns点击查看免费下载相关推荐Java 设计模式实战用 Iterator 模式为二叉搜索树BST实现高效中序遍历迭代器Java 设计模式实战用 Iterator 模式为二叉搜索树BST实现高效中序遍历迭代器 BSTIterator 是 java design patter示例工程教程java-design-patterns 中的迭代器模式Iterator PatternJava 顺序访问聚合对象的实现范式java design patterns 中的迭代器模式Iterator PatternJava 顺序访问聚合对象的实现范式 本文以开源仓库 java d示例工程教程Unity3DTraining 设计模式实战迭代器模式Iterator Pattern原理与 C 实现解析Unity3DTraining 设计模式实战迭代器模式Iterator Pattern原理与 C 实现解析 导读 本文围绕 Unity3DTraining示例工程创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表