[Leetcode] Peek Iterator

Posted on by

Problem:

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().

 Example:
Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].
Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Analysis:

Iterator接口只提供了next() 和 hasNext() 函数

  • next(), 取下一个元素，同时指针移到下下个元素
  • hasNext(), 返回是否还有下一个元素

然后 peek() 函数只取下一个元素，而并不真正移动指针。即，peek如果多次连续被调用，返回的值应该不变 (一直是当前元素)。因此可以用next函数来取下一个元素，并将其cache，所以如果peek多次被调用，只需要返回cache中的值即可。

具体实现如下

  • peek()
    • 如果cache有效，直接返回cache中的值。
    • 否则，调用next函数取下一个元素放在cache中，并将cache设为有效
  • next()
    • 如果cache有效，则返回cache中的值，并将cache置为失效
    • 否则，直接调用next函数
  • hasNext()
    • 如果cache有效，则直接返回true
    • 否则，直接调用hasNext函数

Code:

Leave a Reply