Leetcode 341: Flatten Nested List Iterator

https://leetcode.com/problems/flatten-nested-list-iterator/description/

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,4,6].

Notes:

This is a design problem. There are a lot of ways to implement it. Here I want to list two of them.

The first one is we extract the data from the nested array directly and store them in a queue, then gradually print them out.

There are many similar solutions online, but it all involves copying the data. So the second method is without data copy. Instead, we can use the iterator directly.

For method two, I basically copy the code from the this link:

https://leetcode.com/problems/flatten-nested-list-iterator/discuss/80146/Real-iterator-in-Python-Java-C++

See the code for method 1 below:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        make_stack(nestedList);
    }

    int next() {
        int t = q.front();
        q.pop();
        return t;
    }

    bool hasNext() {
        return q.size();
    }

private:
    queue<int> q;
    void make_stack(vector<NestedInteger> &ns) {
        for(int i=0; i<ns.size(); ++i) {
            if(ns[i].isInteger()) q.push(ns[i].getInteger());
            else make_stack(ns[i].getList());
        }
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

See the code for method 2 below:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        begins.push(nestedList.begin());
        ends.push(nestedList.end());
    }

    int next() {
        hasNext();
        return (begins.top()++)->getInteger();
    }

    bool hasNext() {
        while(begins.size()) {
            if(begins.top() == ends.top()) {
                begins.pop();
                ends.pop();
            }
            else {
                auto x = begins.top();
                if(x->isInteger()) return true;
                begins.top()++;//now the top() iterator points to the next element in the vector<NestedInteger>;
                               //the following two lines means that we gong to finish the nested structures inside the first element first;
                               //when it is done, it will return to the next element (this is why we use stack here);
                               //and it will repeat this to all the elements.
                begins.push(x->getList().begin());
                ends.push(x->getList().end());
            }
        }
        return false;
    }

private:
    stack<vector<NestedInteger>::iterator> begins, ends;
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */