Peeking Iterator
題意:
網友書影 提供的題目大意:
給定一個迭代器類接口,包含方法: next()和hasNext(),設計並實現一個PeekingIterator支持peek()操作 -- 其本質就是把原本應由next()方法返回的元素peek()出來。
這裡有一個例子。假設迭代器初始化為list:[1, 2, 3]。
調用next()得到1,列表的第一個元素。
現在調用peek()然後返回2,下一個元素。在此之後調用next()仍然返回2。
最後一次調用next()返回3,末尾元素。此後調用hasNext()應該返回false。
提示:
考慮"預先獲取"。你可能需要緩存下一個元素。 一個變量夠用嗎?原因是什麼? 通過在next()之前調用peek(),以及在peek()之前調用next()測試你的設計。 關於本問題的一個清晰的實現,可以參考Google的guava庫源代碼。
進一步思考:怎樣拓展你的設計?使之變得通用化,適應所有的類型,而不只是整數?
題解思路:
網友 書影 提供的解題思路:
引入兩個額外的變量nextElement和peekFlag
nextElement標識peek操作預先獲取的下一個元素,peekFlag記錄當前是否已經執行過peek操作
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iterator;
private boolean peekFlag = false; // 標示是否已經執行過peek了
private Integer nextElement = null; // 預先抓下一個
public PeekingIterator(Iterator<Integer> iterator) {
this.iterator = iterator;
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
if (!peekFlag) {
nextElement = iterator.next();
peekFlag = true;
}
return nextElement;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
if (!peekFlag) {
return iterator.next();
}
peekFlag = false;
Integer res = nextElement;
nextElement = null;
return res;
}
@Override
public boolean hasNext() {
return peekFlag || iterator.hasNext();
}
}
update on 2015.12.5
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iterator;
private Integer nextCachedValue = null;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
this.iterator = iterator;
next();
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
return nextCachedValue;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
Integer res = nextCachedValue;
nextCachedValue = iterator.hasNext() ? iterator.next() : null;
return res;
}
@Override
public boolean hasNext() {
return (nextCachedValue != null);
}
}