队列｜ Leetcode 281

Leetcode 分类刷题 —— 队列（Queue）

1、题目描述：

Leetcode 281. Zigzag Iterator 锯齿迭代器

2、解题思路：

目的：给定两个数组，实现交叉依次返回元素值。
方式一：【数组】保存当前遍历的列表的下标，遍历列表里的元素（不推荐）。
方式二：【队列】依次插入数组的迭代器 iterator，进入队列 queue。
每次调用 next 后删除队首元素，如果iterator还有元素再插回队尾（推荐）。

3、代码：

public class ZigzagIterator {
    Queue<Iterator<Integer>> queue = new LinkedList<>();

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        Iterator<Integer> it1 = v1.iterator();
        Iterator<Integer> it2 = v2.iterator();
        if(it1.hasNext()){
            queue.add(it1);
        }
        if(it2.hasNext()){
            queue.add(it2);
        }
    }

    public int next() {
        Iterator<Integer> it = queue.poll();
        int v = it.next();
        if(it.hasNext()){
            queue.add(it);
        }
        
        return v;
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

public class ZigzagIterator {
    
    private List<Iterator<Integer>> list;
    // 标记当前遍历到的list的下标
    private int idx;
    
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        // 将两个列表的迭代器加入到list里去
        list = new ArrayList<>();
        list.add(v1.iterator());
        list.add(v2.iterator());
    }
    
    public int next() {
        hasNext();
        int next = list.get(idx).next();
        idx = (idx + 1) % list.size();
        return next;
    }
    
    public boolean hasNext() {
        // 如果idx这一行有值，那就返回true
        if (list.get(idx).hasNext()){
            return true;
        }
        
        // 否则缓存一下idx赋值给tmp，然后让idx后移，
        // 直到发现了hasNext的那一行返回true，或者回到tmp返回false
        int tmp = idx;
        // 先向下走一步，不然进不了循环。当然用do-while循环也可以
        idx = (idx + 1) % list.size();
        while (idx != tmp) {
            if (list.get(idx % list.size()).hasNext()) {
                return true;
            }
            
            // 向下走一步的时候需要取模，也就是要循环遍历
            idx = (idx + 1) % list.size();
        }
        
        return false;
    }
}

参考文章：
https://www.cnblogs.com/shixuanliu/p/17064500.html