LeetCode[Design]----Peeking Iterator

peeking iterator

 

given an iterator class interface with methods:next()andhasnext(), design and implement a peekingiterator that support thepeek()operation -- it essentially peek() at the element that will be returned by the next call to next().

---

here is an example. assume that the iterator is initialized to the beginning of the list:[1, 2, 3].

callnext()gets you 1, the first element in the list.

now you callpeek()and it returns 2, the next element. callingnext()after thatstillreturn 2.

you callnext()the final time and it returns 3, the last element. callinghasnext()after that should return false.

题目分析：

很多语言中都有迭代器：iterator，这些迭代器一般都有next()和hasnext()方法，next()方法是用来返回迭代器中下一个元素值的，hasnext()方法是判断迭代器中是否含有下一个元素。

但是在这里，我们需要设计一个peekingiterator，这个迭代器除了前面说的两个必备功能外，还有一个叫peek()的方法，peek()方法返回调用next()方法会返回的元素值，即peek()方法能够得到迭代器的下一个元素值，但是其与next()方法不同，peek()的调用并不改变迭代器中指针位置，即可以多次调用peek()方法，而且能够返回同样的元素值，而且peek()方法不影响next()和hasnext()方法的正常使用。这里，你可以类似的理解peek()相当于栈中top()方法，而next()相当于栈中的pop()方法。

所以，给定一个数组[1, 2, 3]，调用next()能够得到第一个元素1，之后调用peek()能够得到第二个元素2，之后再调用next()还是能够得到2，再之后调用next()能够得到3。此时如果调用hasnext()将得到false的返回值。

 

实现思路：

我选择的是python语言，编辑器中提供了peekingiterator类的实现接口。然后我发现，整个peekingiterator类的实现是需要借助iterator的实现的。因为peekingiterator类中构造函数参数引入了iterator，是这样的：def __init__(self, iterator)，所以，peekingiterator类的几个函数的实现是建立在iterator的几个函数的基础上的。

好吧，为了成功测试代码以及能够iterator的构成，我们可以先实现出iterator类。

这是一个简单的类，迭代器的遍历是不可回退的，我们只要使用不断递增的遍历指针就可以实现了。

 

代码为：

 

class iterator(object):
    def __init__(self, nums):
        """
        initializes an iterator object to the beginning of a list.
        :type nums: list[int]
        """
        self.nums = nums
        self.curpoint = 0  # 迭代器的当前指针位置

    def hasnext(self):
        """
        returns true if the iteration has more elements.
        :rtype: bool
        """
        if self.curpoint <= len(nums) - 1:
            return true
        return false

    def next(self):
        """
        returns the next element in the iteration.
        :rtype: int
        """
        if self.hasnext():
            self.curpoint += 1
            return self.nums[self.curpoint - 1]
        else:
            print('error, there is no elements in this iterator.')

在实现了iterator类后，我们来想一下如何构建peekingiterator类。

 

首先看下peek函数。这个函数能够访问迭代器下一个指针指向的值，而且能够多次调用这个函数返回同一个元素的值。我们可以利用iterator函数的next方法先返回迭代器下一个指针指向的值，然后peek函数返回这个值。为了能够多次返回同一个值，我们可以使用一个变量peekval记住这个值，并且使用标记ispeek判断之前是否调用了peek函数，如果调用了那么返回peekval，如果不是，那么返回next方法得到的值，并把返回的值记录在peekval中，设ispeek为已访问。

对于next函数。我们要先判断操作之前是否调用过peek函数，如果调用了那么本次只能返回peekval值，并设ispeek为未访问；如果未调用过，那么调用iterator的next方法得到迭代器的下一个元素值。

对于hasnext函数。一般直接返回iterator的hasnext方法的返回值就好，但是如果之前使用了peek函数，而peek函数会调用next函数，在next函数中会移动迭代器下一个指针的位置，这样会出现在调用peek后，指针已经指向了末尾元素，此时调用iterator的hasnext方法会返回false，而事实上此时迭代器还是有元素的（因为peek不改变迭代器指针的位置）应该返回true。所以在调用hasnext前需要先判断之前是否调用过peek函数，如果调用过那么直接返回true就好了。

 

peekingiterator的代码为：

 

class peekingiterator(object):
    def __init__(self, iterator):
        """
        initialize your data structure here.
        :type iterator: iterator
        """
        self.iterator = iterator
        self.ispeek = false
        self.peekval = 0
        

    def peek(self):
        """
        returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if self.ispeek is false:
            self.peekval = self.iterator.next()
            self.ispeek = true
        return self.peekval
        

    def next(self):
        """
        :rtype: int
        """
        if self.ispeek is true:
            self.ispeek = false
            return self.peekval
        return self.iterator.next()
        

    def hasnext(self):
        """
        :rtype: bool
        """
        if self.ispeek is true:
            return true
        return self.iterator.hasnext()