Actual Nested Iterator using stack in C++


  • 0
    A
    class NestedIterator {
        struct Iterator {
            int i = 0;
            const std::vector<NestedInteger>& list;
            
            Iterator(const std::vector<NestedInteger>& list) : list(list) {}
            
            const NestedInteger& get() const { return list.at(i); }
            void advance() { ++i; }
            bool has_next() { return i < list.size(); }
        };
        
        std::stack<Iterator> iterators;
        int current_val;
        
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            iterators.push(Iterator{nestedList});
            calculateNext();
        }
    
        int next() {
            const int v = current_val;
            calculateNext();
            return v;
        }
    
        bool hasNext() {
            return iterators.size();
        }
        
        inline Iterator& top() {
            return iterators.top();
        }
        
        void calculateNext() {
            while (iterators.size()) {
                if (!top().has_next()) {
                    iterators.pop();
                    continue;
                }
                if (top().get().isInteger()) {
                    break;
                }
                Iterator& current = top();
                iterators.push(Iterator{current.get().getList()});
                current.advance();
            }
            
            if (iterators.size()) {
                current_val = top().get().getInteger();
                top().advance();
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.