281. Zigzag Iterator

Very naive solution, I used two queues and a flag to represent zigzag.

1:  class ZigzagIterator {  
2:  private:  
3:    queue<int> q1;  
4:    queue<int> q2;  
5:    int a;  
6:  public:  
7:    ZigzagIterator(vector<int>& v1, vector<int>& v2) {  
8:      for (int a : v1) {  
9:        q1.push(a);  
10:      }  
11:      for (int a : v2) {  
12:        q2.push(a);  
13:      }  
14:      a = 0;  
15:    }  
16:    int next() {  
17:      int num = 0;  
18:      if (q1.empty()) {  
19:        int num = q2.front();  
20:        q2.pop();  
21:        return num;  
22:      }  
23:      if (q2.empty()) {  
24:        int num = q1.front();  
25:        q1.pop();  
26:        return num;  
27:      }  
28:      if (a == 0) {  
29:        num = q1.front();  
30:        q1.pop();  
31:        a = 1;  
32:      } else {  
33:        num = q2.front();  
34:        q2.pop();  
35:        a = 0;  
36:      }  
37:      return num;  
38:    }  
39:    bool hasNext() {  
40:      return !q1.empty() || !q2.empty();  
41:    }  
42:  };  
43:  /**  
44:   * Your ZigzagIterator object will be instantiated and called as such:  
45:   * ZigzagIterator i(v1, v2);  
46:   * while (i.hasNext()) cout << i.next();  
47:   */  

Well, don't have to use queue actually. Two vectors are good enough and the code looks more concise.

1:  class ZigzagIterator {  
2:  private:  
3:    vector<int> v1;  
4:    vector<int> v2;  
5:    int i1;  
6:    int i2;  
7:    int flag;  
8:  public:  
9:    ZigzagIterator(vector<int>& v1, vector<int>& v2) {  
10:      this->v1 = v1;  
11:      this->v2 = v2;  
12:      i1 = i2 = 0;  
13:      flag = 1;  
14:    }  
15:    int next() {  
16:      int ret = 0;  
17:      if (i1 == v1.size()) ret = v2[i2++];  
18:      else if (i2 == v2.size()) ret = v1[i1++];  
19:      else {  
20:        if (flag == 1) { ret = v1[i1++]; flag = 2; }  
21:        else { ret = v2[i2++]; flag = 1; }  
22:      }  
23:      return ret;  
24:    }  
25:    bool hasNext() {  
26:      return i1 != v1.size() || i2 != v2.size();  
27:    }  
28:  };  
29:  /**  
30:   * Your ZigzagIterator object will be instantiated and called as such:  
31:   * ZigzagIterator i(v1, v2);  
32:   * while (i.hasNext()) cout << i.next();  
33:   */