By

文章目录
  1. 迭代器模式

迭代器模式

  • 提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象的内部表示。
    Iterator

  • 本示例实现了二叉树的前中后序遍历的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
public interface CommonIterator<E> {
    E first();
    E next();
    Boolean isDone();
}
public interface Tree {
    CommonIterator createFrontIndexIterator();
    CommonIterator createMiddleIndexIterator();
    CommonIterator createBackIndexIterIterator();
}
public class Node implements Tree{
    public Node left;
    public Node right;
    public String name;
    public Node(Node left, Node right, String name) {
        this.left = left;
        this.right = right;
        this.name = name;
    }
    public Node(String name) {
        this.name = name;
    }
    public CommonIterator<Node> createFrontIndexIterator(){
        return  new FrontIndexIter(this);
    }
    public CommonIterator<Node> createMiddleIndexIterator(){
        return  new MiddleIndexIter(this);
    }
    public CommonIterator<Node> createBackIndexIterIterator(){
        return  new BackIndexIter(this);
    }
}
public class FrontIndexIter implements CommonIterator<Node> {
    private final Node root;
    private Node cursor = null;
    private Boolean isDone = false;
    private Stack<Node> stack;
    public FrontIndexIter(Node root) {
        this.root = root;
        stack = new Stack<>();
        cursor = root;
        stack.push(cursor);
    }
    @Override
    public Node first() {
        return root;
    }
    @Override
    public Node next() {
        if (stack.isEmpty()) {
            isDone = true;
            return null;
        }
        Node top=stack.pop();
        cursor = top.right;
        if (cursor!=null){
            stack.push(cursor);
        }
        cursor = top.left;
        if (cursor!=null){
            stack.push(cursor);
        }
        return top;
    }
    @Override
    public Boolean isDone() {
        return isDone;
    }
}
public class MiddleIndexIter implements CommonIterator<Node> {
    private final Node root;
    private Node cursor = null;
    private Boolean isDone = false;
    private Stack<Node> stack;
    public MiddleIndexIter(Node root) {
        this.root = root;
        stack = new Stack<>();
        cursor = root;
        while (cursor != null) {
            stack.push(cursor);
            cursor = cursor.left;
        }
    }
    @Override
    public Node first() {
        Node res = root;
        while ((res = res.left) != null) {
        }
        return res;
    }
    @Override
    public Node next() {
        if (stack.isEmpty()) {
            isDone = true;
            return null;
        }
        Node top = stack.peek();
        stack.pop();
        cursor = top.right;
        while (cursor != null) {
            stack.push(cursor);
            cursor = cursor.left;
        }
        return top;
    }
    @Override
    public Boolean isDone() {
        return isDone;
    }
}
public class BackIndexIter implements CommonIterator<Node> {
    private final Node root;
    private Node cursor = null;
    private Boolean isDone = false;
    private Stack<Node> stack;
    public BackIndexIter(Node root) {
        this.root = root;
        stack = new Stack<>();
        cursor = root;
        while (cursor != null) {
            stack.push(cursor);
            cursor = cursor.left;
        }
    }
    @Override
    public Node first() {
        Node res = root;
        while ((res = res.left) != null) {
        }
        return res;
    }
    @Override
    public Node next() {
        if (stack.isEmpty()) {
            isDone = true;
            return null;
        }
        Node top = stack.peek();
        stack.pop();
        if (!stack.isEmpty()) {
            cursor = stack.peek();
            if ((cursor = cursor.right) != null && cursor != top) {
                while (cursor != null) {
                    stack.push(cursor);
                    cursor = cursor.left;
                }
            }
        }
        return top;
    }
    @Override
    public Boolean isDone() {
        return isDone;
    }
}
public class App {
    public static void main(String[] args) {
        Node one = new Node(
                new Node(new Node(new Node("8"),null,"3"), new Node(new Node("6"), new Node("7"), "4"), "2"),
                new Node(new Node("9"),null,"5"), "1");
        CommonIterator<Node> iter = one.createFrontIndexIterator();
        Node d;
        while (!iter.isDone() && (d = iter.next()) != null) {
            System.out.print(d.name+" ");//1 2 3 8 4 6 7 5 9
        }
        System.out.println();
        iter = one.createMiddleIndexIterator();
        while (!iter.isDone() && (d = iter.next()) != null) {
            System.out.print(d.name+" ");//8 3 2 6 4 7 1 9 5
        }
        System.out.println();
        iter = one.createBackIndexIterIterator();
        while (!iter.isDone() && (d = iter.next()) != null) {
            System.out.print(d.name+" ");//8 3 6 7 4 2 9 5 1
        }
    }
}
文章目录
  1. 迭代器模式