Peek Iterator

来源：一亩三分地

原帖：http://www.fgdsb.com/2015/01/25/peek-iterator/

题目：
写一个PeekIterator，包装一个普通的Iterator，要实现peek()方法，返回当前iterator指向的元素，但是不能移动它。除此之外也要实现has_next()和next()方法。
PeekIterator可以用普通iterator的get_next()来获得，但是要记录下来，下一次调用get_next的时候直接返回上一次peek的即可。

代码：

 class Iterator {  
 public:  
     Iterator(vector<int>& num) : data(move(num)), size(0) {}  
     bool has_next() {return size < data.size();}  
     int get_next() {  
         return data[size++];  
     }  
 private:  
     vector<int> data;  
     int size;  
 };  
   
 class PeekIterator {  
 public:  
     PeekIterator(vector<int>& num) : iter(num) {}  
     bool has_next() {  
         iter.has_next() || !peek.empty();  
     }  
   
     int get_next() {  
         if (!peek.empty()) {  
             int ret = peek.back();  
             peek.pop_back();  
             return ret;  
         }  
         return iter.get_next();  
     }  
   
     int get_peek() {  
         if (!peek.empty()) {  
             return peek.back();  
         }  
         int ret = iter.get_next();  
         peek.push_back(ret);  
         return ret;  
     }  
   
 private:  
     vector<int> peek;  
     Iterator iter;  
 };  

173 Binary Search Tree Iterator

来源：Leetcode

原帖：https://leetcode.com/problems/binary-search-tree-iterator/

题目：
Design an iterator over a binary search tree with the following properties: Elements are visited in ascending order (i.e. an inorder traversal) next() and hasNext() queries run in O(1) time in average.
Example
For the following binary search tree, inorder traversal by using iterator is [1, 6, 10, 11, 12]

          10

        /     \

     1          11

        \           \

           6           12


代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class BSTIterator {  
 public:  
   BSTIterator(TreeNode *root) {  
     cur = root;  
   }  
   
   /** @return whether we have a next smallest number */  
   bool hasNext() {  
     return cur || !s.empty();    
   }  
   
   /** @return the next smallest number */  
   int next() {  
     while (cur || !s.empty()) {  
       if (cur) {  
         s.push(cur);  
         cur = cur->left;  
       } else if (!s.empty()) {  
         TreeNode* n = s.top();   
         s.pop();  
         cur = n->right;  
         return n->val;  
       }  
     }  
   }  
     
 private:  
   TreeNode* cur;  
   stack<TreeNode*> s;  
 };