刷leetcode的时候看到这么道题，
这个NestedInteger很明显组成了一棵树，并且我们只要输出叶子节点。于是一个DFS把所有元素抽成一个List，再生成一个迭代器在实现要求。
public class NestedIterator implements Iterator<Integer> {
Iterator<Integer> iterator;
List<Integer> list = new LinkedList<>();
public NestedIterator(List<NestedInteger> nestedList) {
iterate(nestedList);
iterator = list.iterator();
}
public void iterate(List<NestedInteger> nestedList){
for(NestedInteger n : nestedList) {
if (n.isInteger()){
list.add(n.getInteger());
} else{
iterate(n.getList());
}
}
}
@Override
public Integer next() {
return iterator.next();
}
@Override
public boolean hasNext() {
return iterator.hasNext();
}
}
但是如果数据很大，我们又只要迭代一小部分满足条件的元素之后，就中止迭代，那么这种预加载的模式就会浪费时间在构造上，所以应该有一个懒加载模式。
用一个栈来存储迭代器，栈顶就是当前的迭代器。
public class NestedIterator implements Iterator<Integer> {
Deque<Iterator<NestedInteger>> dq = new LinkedList<>();
Integer cur;
public NestedIterator(List<NestedInteger> nestedList) {
dq.push(nestedList.iterator());
}
@Override
// 非幂等
public Integer next() {
Integer res = cur;
cur = null;
return res;
}
@Override
// 幂等
public boolean hasNext() {
if (cur != null) {
return true;
}
while (dq.size() > 0){
Iterator<NestedInteger> it = dq.peek();
if (it.hasNext()){
NestedInteger i = it.next();
if (i.isInteger()){
cur = i.getInteger();
return true;
} else {
dq.push(i.getList().iterator());
}
} else {
dq.pop();
}
}
return false;
}
}
这个实现是在hasNext()取值， 像Java的SPI机制的迭代也是在hasNext()取值。