题目

flattern-nested-list-iterator/

算法

* stack

* dqueue

* 优化

代码

* stack

class NestedIterator {

public:

    NestedIterator(vector<NestedInteger> &nestedList) {

        for (int i = nestedList.size() - 1; i >= 0; --i) {

            s.push(nestedList[i]);

        }

    }

    int next() {

        NestedInteger t = s.top(); s.pop();

        return t.getInteger();

    }

    bool hasNext() {

        while (!s.empty()) {

            NestedInteger t = s.top(); 

            if (t.isInteger()) return true;

            s.pop();

            for (int i = t.getList().size() - 1; i >= 0; --i) {

                s.push(t.getList()[i]);

            }

        }

        return false;

    }

private:

    stack<NestedInteger> s;

};

* dqueue

class NestedIterator {

public:

    NestedIterator(vector<NestedInteger> &nestedList) {

        for (auto a : nestedList) {

            d.push_back(a);

        }

    }

    int next() {

        NestedInteger t = d.front(); d.pop_front();

        return t.getInteger();

    }

    bool hasNext() {

        while (!d.empty()) {

            NestedInteger t = d.front();

            if (t.isInteger()) return true;

            d.pop_front();

            for (int i = 0; i < t.getList().size(); ++i) {

                d.insert(d.begin() + i, t.getList()[i]);

            }

        }

        return false;

    }

private:

    deque<NestedInteger> d;

};

* 优化

class NestedIterator {

public:

    NestedIterator(vector<NestedInteger> &nestedList) {

        make_queue(nestedList);

    }

    int next() {

        int t = q.front(); q.pop();

        return t; 

    }

    bool hasNext() {

        return !q.empty();

    }



private:

    queue<int> q;

    void make_queue(vector<NestedInteger> &nestedList) {

        for (auto a : nestedList) {

            if (a.isInteger()) q.push(a.getInteger());

            else make_queue(a.getList());

        }

    }

};