Design an iterator that supports a peek operation in addition to hasNext and next.

Implement the PeekingIterator class:

Input:
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output:
[null, 1, 2, 2, 3, false]

Explanation:
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // returns 1 and moves the pointer to the next element [1,2,3]
peekingIterator.peek();    // returns 2 without moving the pointer [1,2,3]
peekingIterator.next();    // returns 2 and moves the pointer to the next element [1,2,3]
peekingIterator.next();    // returns 3 and moves the pointer to the next element [1,2,3]
peekingIterator.hasNext(); // returns False

Follow-up: How would you extend your design to make it generic so that it works with all types, rather than only integers?

Analysis

#

The main difficulty is that the Iterator data structure provided by the original problem exposes only these two interfaces:

• int next()
• bool hasNext()

Our data structure must add a third interface, int peek(), on top of them.

This creates a problem: every call to next() unquestionably moves the iterator forward by one position, while a call to peek() does not.

One straightforward idea is to save a number every time next() is called and use it as the return value for the next call to peek(). However, that approach has a problem.

As Example 1 shows, calling peek() does not move the pointer, but it still retrieves the value of the next element. The challenge is to obtain the next element’s value without moving the pointer, even though next() always moves it.

The approach is to keep the next element’s value in a variable. If peek() is called, return this stored value. If next() is called, return the stored value as well, then update the stored value to the following element.

C++ Code

#

class PeekingIterator : public Iterator {
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        flag = Iterator::hasNext();
        if (flag) {
            nextElement = Iterator::next();
        }
    }

    int peek() {
        return nextElement;
    }

    int next() {
        int ret = nextElement;
        flag = Iterator::hasNext();
        if (flag) {
            nextElement = Iterator::next();
        }
        return ret;
    }

    bool hasNext() const {
        return flag;
    }
private:
    int nextElement;
    bool flag;
};