题目描述

给定一个迭代器类的interface，包含两个函数：next() 和 hasNext()，请实现一个新迭代器 PeekingIterator， 支持：

• peek() ：返回下一个元素，但不更新迭代器。

进一步: 如何扩展代码，使得可以处理所有类型的迭代器，而非只能处理整型的？

样例

假设迭代器被初始化成链表 [1, 2, 3] 的头结点。

调用 next() 函数会得到链表的第一个元素1；
调用 peek() 函数会得到2，是下一个元素。然后调用 next() 仍然会返回2；
调用 next() 函数会返回3，是链表的最后一个元素；
调用 hasNext() 函数会返回 false。

算法

(缓存) $O(1)$

在新的类 PeekingIterator 中缓存两个变量：int _next; 和 bool _has_next; 分别存储下一个元素和是否存在下一个元素。

PeekingIterator 初始化时先更新这两个变量；
peek() 函数直接返回缓存的下一个元素 _next；
hasNext() 函数直接返回缓存的 _has_next；
next() 函数稍微麻烦一点，需要返回缓存的 _next，同时不要忘记更新 _next 和 _has_next；

如果想处理所有类型的迭代器，我们需要利用C++中的template机制。

时间复杂度分析：所有操作均只涉及常数次操作，所以时间复杂度是 $O(1)$。

C++ 代码

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
    Data* data;
public:
    Iterator(const vector<int>& nums);
    Iterator(const Iterator& iter);
    virtual ~Iterator();
    // Returns the next element in the iteration.
    int next();
    // Returns true if the iteration has more elements.
    bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
    int _next;
    bool _has_next;

    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        // Initialize any member here.
        // **DO NOT** save a copy of nums and manipulate it directly.
        // You should only use the Iterator interface methods.
        _has_next = Iterator::hasNext();
        if (_has_next)
            _next = Iterator::next();
    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {
        return _next;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    int next() {
        int res = _next;
        _has_next = Iterator::hasNext();
        if (_has_next)
            _next = Iterator::next();
        return res;
    }

    bool hasNext() const {
        return _has_next;
    }
};