import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * Given a nested list of integers, implement an iterator to flatten it.
 * <p>
 * Each element is either an integer, or a list -- whose elements may also be integers or other lists.
 * <p>
 * Example 1:
 * Given the list [[1,1],2,[1,1]],
 * <p>
 * By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:
 * [1,1,2,1,1].
 * <p>
 * Example 2:
 * Given the list [1,[4,[6]]],
 * <p>
 * By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
 * <p>
 * Tags: Stack, Design
 * Similar Problems: (M) Flatten 2D Vector, (M) Zigzag Iterator
 */
public class FlattenNestedListIterator {

    /**
     * This is the interface that allows for creating nested lists.
     * You should not implement it, or speculate about its implementation
     */
    public interface NestedInteger {

        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger();

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger();

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }

    public class NestedIterator implements Iterator<Integer> {

        private Stack<NestedInteger> stack;

        public NestedIterator(List<NestedInteger> nestedList) {
            stack = new Stack<>();
            flattenList(nestedList);
        }

        @Override
        public Integer next() {
            return hasNext() ? stack.pop().getInteger() : null;
        }

        @Override
        public boolean hasNext() {
            while (!stack.isEmpty()) {
                if (stack.peek().isInteger()) return true;
                flattenList(stack.pop().getList());
            }
            return false;
        }

        private void flattenList(List<NestedInteger> list) {
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
    }

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
}

@@ -1,29 +1,107 @@
-import java.util.Iterator
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.ArrayDeque;%0Aimport java.util.Deque
 ;%0Aim
@@ -115,20 +115,24 @@
 va.util.
-List
+Iterator
 ;%0Aimport
@@ -142,21 +142,20 @@
 va.util.
-Stack
+List
 ;%0A%0A/**%0A 
@@ -1665,21 +1665,21 @@
 private 
-Stack
+Deque
 %3CNestedI
@@ -1691,16 +1691,37 @@
 r%3E stack
+ = new ArrayDeque%3C%3E()
 ;%0A%0A     
@@ -1783,43 +1783,8 @@
 ) %7B%0A
-            stack = new Stack%3C%3E();%0A
     
@@ -2094,20 +2094,60 @@
 ()) 
-return true;
+%7B%0A                    return true;%0A                %7D
 %0A   

update flatten nested list iterator