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].

class ZigzagIterator {
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        it1 = v1.begin();
        end1 = v1.end();
        it2 = v2.begin();
        end2 = v2.end();
        v1_turn = it1 == end1 ? false : true;
    }
    
    int next() {
        if (hasNext()) {
            if (v1_turn || it2 == end2) {
                v1_turn = it2 == end2 ? true : false;
                return *it1++;
            } else if (!v1_turn || it1 == end1) {
                v1_turn = it1 == end1 ? false : true;
                return *it2++;
            }
        }
        return -1;
    }
    
    bool hasNext() {
        if (it1 != end1 || it2 != end2) {
            return true;
        } else return false;
    }
    private:
    vector<int>::iterator it1, end1, it2, end2;
    bool v1_turn;
};

class ZigzagIterator {
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        if (!v1.empty()) q.push(make_pair(v1.begin(), v1.end()));
        if (!v2.empty()) q.push(make_pair(v2.begin(), v2.end()));
    }

    int next() {
        pair<vector<int>::iterator, vector<int>::iterator > t = q.front();
        vector<int>::iterator it = t.first, endIt = t.second;
        q.pop();
        if (it + 1 != endIt) q.push(make_pair(it + 1, endIt));
        return *it;
    }

    bool hasNext() {
        return !q.empty();
    }
private:
    queue<pair<vector<int>::iterator, vector<int>::iterator> > q;
};