LeetCode Design：Peeking Iterator 迭代器設計

問題描述

給定一個擁有 next() 和 hasNext() 的 Iterator 接口，設計一個 PeekingIterator，增加 peek() 方法：返回下一個元素但不移動指針。多次調用 peek() 返回相同值，不影響 next()/hasNext() 行為。

核心思路：緩存下一個元素

維護兩個狀態變量：

• peeked：是否已緩存下一個元素
• peekVal：緩存的元素值

Python 實現

class Iterator:
    def __init__(self, nums):
        self.nums = nums
        self.idx = 0
    
    def hasNext(self):
        return self.idx < len(self.nums)
    
    def next(self):
        if self.hasNext():
            val = self.nums[self.idx]
            self.idx += 1
            return val
        raise StopIteration()

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self.peeked = False
        self.peekVal = None
    
    def peek(self):
        if not self.peeked:
            self.peekVal = self.iterator.next()
            self.peeked = True
        return self.peekVal
    
    def next(self):
        if self.peeked:
            self.peeked = False
            return self.peekVal
        return self.iterator.next()
    
    def hasNext(self):
        return self.peeked or self.iterator.hasNext()

C++ 實現

class PeekingIterator : public Iterator {
    bool hasPeeked = false;
    int peekedVal;
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {}
    
    int peek() {
        if (!hasPeeked) {
            peekedVal = Iterator::next();
            hasPeeked = true;
        }
        return peekedVal;
    }
    
    int next() {
        if (hasPeeked) {
            hasPeeked = false;
            return peekedVal;
        }
        return Iterator::next();
    }
    
    bool hasNext() const {
        return hasPeeked || Iterator::hasNext();
    }
};

關鍵邏輯解析

示例演示

nums = [1,2,3]
it = PeekingIterator(nums)
it.next()    -> 1
it.peek()    -> 2  (緩存 2)
it.peek()    -> 2  (直接返回緩存)
it.next()    -> 2  (消費緩存)
it.next()    -> 3
it.hasNext() -> false

設計要點

• 不修改底層迭代器接口：組合而非繼承（Python），或繼承並重寫（C++）
• 狀態機清晰：peeked 標記避免重複調用底層 next()
• 邊界處理：底層無元素時 peek()/next() 行為依賴底層實現（拋異常或未定義）