341. Flatten Nested List Iterator

• 재귀 구조로 구현된 숫자 목록을 순회하는 iterator를 구현하는 문제.

• 현재 list와 위치를 저장하는 객체 Entry 를 만들고 stack을 사용하여 각 중첩된 list의 위치 정보를 표현한다.

• List에서 다음 숫자 위치를 가리키는 Entry를 찾는 함수 ensureNext를 구현한다.
• Stack의 마지막 Entry를 기준으로
• iterator가 현재 list의 마지막을 가리키는 경우 stack에서 제거한다.
• iterator가 가리키는 항목이 숫자인 경우 현재 Entry를 돌려준다.
• iterator가 가리키는 항목이 목록인 경우
• 참조를 저장해둔다 nextList
• iterator를 하나 증가시킨다
• Stack에 nextList에 대한 entry를 추가한다.

• hasNext에서는 ensureNext에서 돌려주는 entry가 존재 (not null)하는지 확인한다.

• next에서는 ensureNext에서 돌려주는 entry의 값을 읽고 entry의 iterator를 증가시킨다.

/**
 * // 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:
    using ListPtr = vector<NestedInteger>*;
    using ListItr = vector<NestedInteger>::iterator;
    using Entry = pair<ListPtr, ListItr>;

    NestedIterator(vector<NestedInteger> &nestedList) {
        entries.emplace_back(&nestedList, nestedList.begin());
    }
    
    int next() {
        auto* entry = ensureNext();
        if (entry == nullptr) return -1;
        int result = entry->second->getInteger();
        ++(entry->second);
        return result;
    }
    
    bool hasNext() {
        return ensureNext() != nullptr;
    }

    Entry* ensureNext() {
        while (!entries.empty()) {
            auto& entry = entries.back();
            if (entry.second == entry.first->end()) {
                entries.pop_back();
                continue;
            }
            if (entry.second->isInteger())
                return &entry;
            auto& nextList = entry.second->getList();
            ++entry.second;
            entries.emplace_back(&nextList, nextList.begin());
        }
        return nullptr;
    }

private:
    vector<Entry> entries;
};

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