L家面试题 iterator for nested integer求

http://www.mitbbs.com//article_t/JobHunting/32921023.html

发信人: yuxrose (鱼香肉丝), 信区: JobHunting
标  题: L家面试题 iterator for nested integer求讨论
发信站: BBS 未名空间站 (Sun Mar 29 14:22:37 2015, 美东)

L家最爱考的面试题之一就是nested integer了，
还爱考各种iterator的implementation
这题是把两个最爱合在一起了。。。。感觉很有可能出，但网上没找到满意的答案.

题目是这样的
eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6

这个data structure的interface是这样的
public interface Data<T> {
    // Does this Data hold a collection?
    public boolean isCollection();
    // Returns the collection contained by this Data, or null if it is a
single element
    public Collection<Data<T>> getCollection();
    // Returns the single element contained by this Data, or null if it is a
collection
    public T getElement();
}

我的思路把iterator放在一个stack里，有点像Preorder traversal，如果是element就
存进一个暂时的variable store里，call next的时候就return这个，如果是
isCollection的话，就再push stack里。但我对什么时候pop有点糊涂，其实我很怕用
generic type写东西，特别抽象，只好自己脑补成一个list

下面是我的solution,还请大家给点建议

public class iterator_nestedmap<T>{
    private Stack<Iterator<Data<T>>> stack;
    private T store;
    public iterator_nestedmap(Collection<Data<T>> collection){
        stack = new Stack<Iterator<Data<T>>>();
        stack.push(collection.iterator());
    }
   
    public boolean hasNext(){
        if(store != null){
            return true;
        }
        while(!stack.isEmpty()){
            Iterator<Data<T>> iter = stack.peek();
            if(!iter.hasNext()){
                stack.pop();
                continue;
            }
            Data<T> element = iter.next();
            if(element.isCollection()){
                Collection<Data<T>> col = element.getCollection();
                stack.push(col.iterator());
            }
            else{
                store = element.getElement();
                return true;
            }
        }
        return false;
    }
   
    public T next(){
        T result = null;
        if(hasNext() || store != null){
            result = store;
            store = null;
            return result;
        }
        return null;
    }
}

--
我用奔跑告诉你，我不回头
※ 修改:·yuxrose 於 Mar 29 14:23:21 2015 修改本文·[FROM: 76.]