Iterator

算法思路：

hasNext, next都涉及计算下一个元素，大部分题目是先计算再返回。只有BST是先返回再计算，因为BST的下一个节点取决于要返回的节点，若返回了，就无法知道下一个节点。

注意事项：

1. hasNext中，while循环找到下一个符合条件的元素
2. next中取值后指针要后移。

Python代码：

def __init__(self):
	self.stack = []
	<add to stack>

def next(self) -> int:
	if self.hasNext():
		return self.stack.pop()
	return None

def hasNext(self) -> bool:
	while <until find the next element>:
	   <calculate>
	return <next element>

应用题型：

LeetCode 251 Flatten 2D Vector
LeetCode 281 Zigzag Iterator
LeetCode 341 Flatten Nested List Iterator
LeetCode 173 Binary Search Tree Iterator

算法分析：

next操作时间复杂度为O(N + V)/N或O(1)，N为所有数，V为复合结构数