Iterator（迭代器）

# python
class MyIterator:
    def __init__(self, data):
        self.data = data
        self.idx = 0

    def hasNext(self):
        return self.idx < len(self.data)

    def next(self):
        val = self.data[self.idx]
        self.idx += 1
        return val

// java
// IDEA: idiom A - buffer one element ahead; hasNext() is a pure test.
//       Use an explicit boolean flag, NOT a null sentinel, so a stream that
//       legitimately contains null still works.
// time = O(1) amortized per next(), space = O(1) extra
class BufferedIterator<T> {
    private final Iterator<T> src;
    private T buffer;
    private boolean hasBuffered;

    BufferedIterator(Iterator<T> src) {
        this.src = src;
        advance();                       // prime once
    }

    private void advance() {             // the ONLY place that pulls from src
        hasBuffered = src.hasNext();
        buffer = hasBuffered ? src.next() : null;
    }

    public boolean hasNext() { return hasBuffered; }   // pure, idempotent

    public T peek() {                                  // non-destructive
        if (!hasBuffered) throw new NoSuchElementException();
        return buffer;
    }

    public T next() {
        if (!hasBuffered) throw new NoSuchElementException();
        T ret = buffer;
        advance();
        return ret;
    }
}

# python
# IDEA: idiom B - do the lazy work inside hasNext(); it must be safe to call twice.
#       hasNext() only UNCOVERS the next element, next() is what removes it.
# time = O(1) amortized per next(), space = O(depth) for the pending stack
class LazyIterator:
    def __init__(self, items):
        self.stack = list(reversed(items))

    def hasNext(self):
        # normalize: pop away anything that is not a yieldable element.
        # re-entrant -> calling it again just re-checks an already-clean top
        while self.stack and not self._is_leaf(self.stack[-1]):
            top = self.stack.pop()
            self.stack.extend(reversed(self._children(top)))
        return len(self.stack) > 0

    def next(self):
        if not self.hasNext():
            raise StopIteration
        return self.stack.pop()          # ONLY next() consumes

    def _is_leaf(self, x):
        return not isinstance(x, list)

    def _children(self, x):
        return x

# python
# LC 284. Peeking Iterator
# IDEA: wrap the given iterator and cache the next value so peek() is non-destructive
class PeekingIterator:
    def __init__(self, iterator):
        self.it = iterator
        self.buffer = self.it.next() if self.it.hasNext() else None

    def peek(self):
        return self.buffer

    def next(self):
        ret = self.buffer
        self.buffer = self.it.next() if self.it.hasNext() else None
        return ret

    def hasNext(self):
        return self.buffer is not None

# python
# LC 341. Flatten Nested List Iterator
# IDEA: keep a stack of NestedInteger; lazily unwrap lists in hasNext()
class NestedIterator:
    def __init__(self, nestedList):
        # push in reverse so the first element ends up on top of the stack
        self.stack = nestedList[::-1]

    def next(self):
        return self.stack.pop().getInteger()

    def hasNext(self):
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack.pop()
            self.stack.extend(top.getList()[::-1])
        return False

// java
// LC 900 - RLE Iterator
// IDEA: cursor (i) on the current run + how many of it are used.
//       While n overflows the remaining part of the run, consume the remainder
//       and jump to the next run. Exhausted -> -1.
// time = O(1) amortized per next() (each run is skipped at most once,
//        so a whole run of calls is O(len(encoding))), space = O(1)
class RLEIterator {
    private final int[] encoding;
    private int i = 0;        // index of the current COUNT
    private long used = 0;    // how many of encoding[i] already consumed

    public RLEIterator(int[] encoding) { this.encoding = encoding; }

    public int next(int n) {
        long k = n;           // long: count and n are both up to 1e9 -> int overflows
        while (i < encoding.length && used + k > encoding[i]) {
            k -= encoding[i] - used;   // eat what is left of this run
            used = 0;
            i += 2;                    // move to the next (count, value) pair
        }
        if (i >= encoding.length) return -1;   // stream exhausted
        used += k;
        return encoding[i + 1];
    }
}

# python
# LC 900 - RLE Iterator
# IDEA: same cursor + used counter; Python ints don't overflow so no cast needed
# time = O(1) amortized per next(), space = O(1)
class RLEIterator:
    def __init__(self, encoding):
        self.enc = encoding
        self.i = 0        # index of the current count
        self.used = 0     # consumed portion of enc[i]

    def next(self, n):
        while self.i < len(self.enc) and self.used + n > self.enc[self.i]:
            n -= self.enc[self.i] - self.used
            self.used = 0
            self.i += 2
        if self.i >= len(self.enc):
            return -1
        self.used += n
        return self.enc[self.i + 1]

// java
// LC 1286 - Iterator for Combination
// IDEA: keep only the k current indices; advance like an odometer.
//       characters is already sorted, so index order == lexicographic order.
// time = O(k) per next(), O(1) hasNext(), space = O(k)  (NOT O(C(n,k)))
class CombinationIterator {
    private final char[] s;
    private final int k;
    private final int[] idx;      // current combination as indices into s
    private boolean done = false;

    public CombinationIterator(String characters, int combinationLength) {
        this.s = characters.toCharArray();
        this.k = combinationLength;
        this.idx = new int[k];
        for (int i = 0; i < k; i++) idx[i] = i;   // first combination = 0,1,...,k-1
    }

    public boolean hasNext() { return !done; }    // pure, idempotent

    public String next() {
        StringBuilder sb = new StringBuilder();
        for (int i : idx) sb.append(s[i]);        // emit CURRENT, then advance

        int i = k - 1;
        while (i >= 0 && idx[i] == i + s.length - k) i--;   // idx[i] maxed out?
        if (i < 0) {
            done = true;                          // last combination just emitted
        } else {
            idx[i]++;
            for (int j = i + 1; j < k; j++) idx[j] = idx[j - 1] + 1;  // reset the tail
        }
        return sb.toString();
    }
}

# python
# LC 1286 - Iterator for Combination
# IDEA: odometer over the k chosen indices; emit current, then step forward
# time = O(k) per next(), O(1) hasNext(), space = O(k)
class CombinationIterator:
    def __init__(self, characters, combinationLength):
        self.s = characters
        self.k = combinationLength
        self.idx = list(range(self.k))
        self.done = False

    def hasNext(self):
        return not self.done

    def next(self):
        res = "".join(self.s[i] for i in self.idx)   # emit current

        i = self.k - 1
        while i >= 0 and self.idx[i] == i + len(self.s) - self.k:
            i -= 1
        if i < 0:
            self.done = True
        else:
            self.idx[i] += 1
            for j in range(i + 1, self.k):
                self.idx[j] = self.idx[j - 1] + 1
        return res

// java
// LC 232 - Implement Queue using Stacks
// IDEA: in-stack absorbs writes, out-stack serves reads; flip only when out is empty
// time = O(1) amortized per op (worst case O(n) for one pop), space = O(n)
class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();

    public void push(int x) { in.push(x); }

    public int pop()  { shift(); return out.pop(); }
    public int peek() { shift(); return out.peek(); }   // the "hasNext must not consume" analogue

    public boolean empty() { return in.isEmpty() && out.isEmpty(); }

    private void shift() {
        if (out.isEmpty()) {            // the guard IS the amortization
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

# python
# LC 232 - Implement Queue using Stacks
# time = O(1) amortized per op, space = O(n)
class MyQueue:
    def __init__(self):
        self.in_st = []
        self.out_st = []

    def push(self, x):
        self.in_st.append(x)

    def _shift(self):
        if not self.out_st:                  # only when drained
            while self.in_st:
                self.out_st.append(self.in_st.pop())

    def pop(self):
        self._shift()
        return self.out_st.pop()

    def peek(self):
        self._shift()
        return self.out_st[-1]

    def empty(self):
        return not self.in_st and not self.out_st