破坏性栈迭代

Question

这是我的堆栈实现。

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0

    def push(self, item):
        node = Node(item)
        if not self.head:
            self.head = node
        else:
            node.next = self.head
            self.head = node
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise ValueError('Popping off an empty stack!')
        item = self.head.val
        self.head = self.head.next
        return item

    def peek(self):
        if self.size == 0:
            raise ValueError('Peeking into an empty stack!')
        return self.head.val

    def __iter__(self):
        return self

    def __next__(self):
        if self.head:
            curr = self.head
        else:
            raise StopIteration()
        self.head = self.head.next
        return curr.val

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


if __name__ == '__main__':
    stack = Stack()
    stack.push(12)
    stack.push(13)
    stack.push(9)
    for item in stack:
        print(item)
    print(stack.peek())

这种方法的问题在于迭代。迭代是具有破坏性的，因此在迭代结束时调用peek会引发错误。 return self.head.val AttributeError: 'NoneType'对象没有属性'val' 如何使迭代不具有破坏性？

- Melissa Stewart

---

谢谢您的接受，但是实际上，您应该接受Tim或Daniel的解决方案，因为它比我的更健壮（尽管我想我的更容易理解一些）。 - PM 2Ring

Python已经自带了堆栈类型collections.deque。它很可能提供您所需的所有功能。 - Bachsau

Answer 1

由于同一堆栈上可以有多个迭代器，因此__iter__必须返回一个迭代器对象，该对象遍历堆栈：

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0

    def push(self, item):
        node = Node(item)
        if self.head:
            node.next = self.head
        self.head = node
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise ValueError('Popping off an empty stack!')
        item = self.head.val
        self.head = self.head.next
        return item

    def peek(self):
        if self.size == 0:
            raise ValueError('Peeking into an empty stack!')
        return self.head.val

    def __iter__(self):
        return StackIterator(self.head)

class StackIterator:
    def __init__(self, head):
        self.head = head

    def __iter__(self):
        return self

    def __next__(self):
        if not self.head:
            raise StopIteration()
        item = self.head.val
        self.head = self.head.next
        return item

- Daniel

Answer 2

问题在于您没有区分可迭代的栈本身和__iter__应该返回的迭代器之间的区别。应该在所述迭代器上调用__next__，而不是在Stack本身上调用。

我提出以下解决方案：

class StackIterator:
    def __init__(self, stack):
        self.head = stack.head

    def __iter__(self):
        return self

    def __next__(self):
        if not self.head:
            raise StopIteration

        current = self.head
        self.head = self.head.next

        return current.val

将Stack中的__next__去掉，并调整__iter__为：

def __iter__(self):
    return StackIterator(self)

演示：

>>> stack = Stack()
>>> stack.push(12)
>>> stack.push(13)
>>> stack.push(9)
>>> 
>>> for x in stack:
...     print(x)
... 
9
13
12
>>> stack.peek()
9

- timgeb

Answer 3

一个简单的方法是给您的 Stack 提供一个可用于迭代的替代头部。我还添加了一个 __len__ 方法来返回 Stack 的大小。

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0

    def __len__(self):
        return self.size

    def push(self, item):
        node = Node(item)
        if not self.head:
            self.head = node
        else:
            node.next = self.head
            self.head = node
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise ValueError('Popping off an empty stack!')
        item = self.head.val
        self.head = self.head.next
        return item

    def peek(self):
        if self.size == 0:
            raise ValueError('Peeking into an empty stack!')
        return self.head.val

    def __iter__(self):
        self.top = self.head
        return self

    def __next__(self):
        if self.top:
            curr = self.top
        else:
            raise StopIteration()
        self.top = self.top.next
        return curr.val

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None    

if __name__ == '__main__':
    stack = Stack()
    stack.push(12)
    stack.push(13)
    stack.push(9)
    print('Size', len(stack))
    for item in stack:
        print(item)
    print(stack.peek())
    stack.push(42)
    print('Size', len(stack))
    for item in stack:
        print(item)

输出

Size 3
9
13
12
9
Size 4
42
9
13
12

在__init__中添加self.top = None可能是一个好主意，尽管这并非绝对必要。你可能希望在名称前加上下划线来标记它为私有名称：self._top。

正如timgeb在评论中所暗示的那样，这种方法有点脆弱，因为我们只能在堆栈上一次执行一个迭代，因为我们只有一个单独的self.top。

---

顺便说一句，你可以稍微优化一下push方法：

def push(self, item):
    node = Node(item)
    if self.head:
        node.next = self.head
    self.head = node
    self.size += 1

- PM 2Ring

---

现在尝试在两个嵌套的 for 循环中遍历相同的栈。 :) - timgeb

@timgeb 嘿，我说它很“简单”，但我没说它很健壮。 :D - PM 2Ring

你的回答仍然有助于学习为什么标准的Python可迭代对象（如列表）本身不是迭代器，所以+1 :) - timgeb

@timgeb，你和Daniel几乎同时发布了一个优秀的解决方案，所以我想你们两个都应该得到一分。 - PM 2Ring