Flatten Nested List Iterator

Problem

You are given a nested list where each element is either an integer or another nested list, to arbitrary depth. Elements are exposed only through a NestedInteger interface:

• isInteger(): True if this element holds a single integer.
• getInteger(): the integer, if isInteger() is true.
• getList(): the list of child NestedInteger elements, if isInteger() is false.

Implement NestedIterator with __init__(nestedList), next() returning the next integer in left-to-right depth-first order, and hasNext() returning whether any integers remain. Callers may invoke hasNext() any number of times (including zero) between calls to next(), and will only call next() when an integer remains.

• The top-level list holds at most a few hundred elements.
• Integer values fit in a signed 32-bit range.
• Nested lists may be empty at any depth.

Examples

• [[5,5],9,[5,5]] → next() repeatedly yields 5, 5, 9, 5, 5.
• [2,[7,[8]]] → yields 2, 7, 8.
• [[], [[]], 3, []] → yields only 3; hasNext() must skip over the empty lists rather than reporting there is a next element.

Hints

1. Recursively flattening everything into an array in the constructor works, but what if the structure is enormous or the caller only reads the first few elements?
2. Depth-first traversal that can pause: replace recursion with an explicit stack.
3. Push the top-level elements onto a stack in reverse order. In hasNext, while the top is a list, pop it and push its children in reverse; stop when the top is an integer or the stack is empty.