281 Zigzag iterator

這題最簡單的做法就是在constructor裡面就把vector的element依序parse並存放到內部的queue裡面，那next()跟hasNext()就可以直接從queue裡面取出需要的element。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class ZigzagIterator {
public:
    vector<int>::iterator it_first;
    vector<int>::iterator it_second;

    ZigzagIterator(vector<int>& v1, vector<int>& v2)
    {
        it_first = v1.begin();
        it_second = v2.begin();

        while(it_first != v1.end() || it_second != v2.end())
        {
            if(it_first != v1.end())
            {
                q.push(*it_first);
                it_first++;
            }

            if(it_second != v2.end())
            {
                q.push(*it_second);
                it_second++;
            }
        }
    }

    int next() 
    {
        int next_element;

        if(!q.empty())
        {
            next_element = q.front();
            q.pop();
            return next_element;
        }
    }

    bool hasNext()
    {
        return q.empty() ? false : true;
    }

    void printQueue()
    {
        while(!q.empty())
        {
            cout << q.front() << " ";
            q.pop();
        }    

        cout << endl;
    }

private:
    queue<int> q;
};

int main() {
    int arr[2] = {1,2};
    vector<int> v1 (arr, arr + sizeof(arr) / sizeof(arr[0]) );

    int arr2[4] = {3,4,5,6};
    vector<int> v2 (arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]) );

    ZigzagIterator z(v1, v2);
    while (z.hasNext())
        cout << z.next() << " ";
    cout << endl;

#if 0
    ZigzagIterator z(v1, v2);
    z.printQueue();
#endif
#if 0
    ZigzagIterator* z = new ZigzagIterator(v1, v2);
    z->printQueue();
#endif

    return 0;
}

不過如果有k個vector，上面的程式碼就難以擴展，有一個聰明的做法是儲存兩個vector的iterator pair，每次取next()的時候再把iterator pair塞到queue的後面。

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

    int next() {
        vector<int>::iterator it = Q.front().first;
        vector<int>::iterator endIt = Q.front().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;
};