# 281. Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

Example:

Input:
v1 = [1,2]
v2 = [3,4,5,6] 

Output: [1,3,2,4,5,6]

Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,3,2,4,5,6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question: The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example:

Input:
[1,2,3]
[4,5,6,7]
[8,9]

Output: [1,4,8,2,5,9,3,6,7].

# Solution

Approach 1: for the follow up generalization, store iterators in a queue.

# Code (Python)

Approach 1:

# An wrapper implementation in Python with next() and has_next() methods
# In native python you need to implement __iter__() returning self, and __next__() returning the next element or raise StopIteration
class Iterator:
    def __init__(self, iterable):
        self._iterator = iter(iterable)
        self._test_next()
    
    def _test_next(self):
        try:
            self._next_val = next(self._iterator)
            self._has_next = True
        except StopIteration as e:
            self._next_val = None
            self._has_next = False
    
    def next(self):
        if self._has_next:
            val = self._next_val
            self._test_next()
            return val
        else:
            raise StopIteration()
    
    def has_next(self):
        return self._has_next

# actual ZigzagIterator implementation
from collections import deque
class ZigzagIterator():
    
    def __init__(self, lists):
        self._queue = deque([Iterator(item) for item in lists])
        self._has_next = False
        self._next = None
        self._set_next()
          
    def _set_next(self):
        # get next item
        while self._queue:
            iterator = self._queue.popleft()
            if iterator.has_next():
                self._next = iterator.next()
                self._has_next = True
                self._queue.append(iterator)
                return
        self._next = None
        self._has_next = False
    
    def next(self):
        if self._has_next:
            val = self._next
            self._set_next()
            return val
        else:
            raise StopIteration()
    
    def has_next(self):
        return self._has_next
        
it = ZigzagIterator([[1,3,5], [2, 4], [100], []])
while it.has_next():
    print(it.next())

# Code (C++)

Approach 1:

Approach 2: