341. Flatten Nested List Iterator

這題系統設計題, 用stack

但我們在處理stack從最後一個塞, 才可以確保第一個在最上面

因為在用next前, 會用hasNext

所以在這邊我們可以假設next都可以拿到Stack的最上層, 也都是integer

而hasNext, 我們先去在最上層是不是integer, 是的話直接回傳true

不是的話, 我們在把最上層的vector解開, 然後一樣從最後面塞入stack, 然後放完後再從新檢查一次最上層, 直到是integer

/**
 * // 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> &nL) {
        for(int i = nL.size() - 1;i>=0;i--){
            st.push(nL[i]);
        }
    }
    
    int next() {
        auto t = st.top();
        st.pop();
        return t.getInteger();
    }
    
    bool hasNext() {
        while(!st.empty()){
            auto t = st.top();
            if(t.isInteger()){
                return true;
            }
            st.pop();
            auto arr = t.getList();
            for(int i = arr.size() - 1; i >=0;i--){
                st.push(arr[i]);
            }
        }
        return false;
    }
    stack<NestedInteger> st;
};
/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */