破坏性堆栈迭代

问题内容：

这是我的Stack实现。

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' object has no attribute 'val' 如何使迭代无损？

问题答案：

一种简单的方法可以为您的Stack提供一个可用于迭代的替代头。我还添加了一个__len__方法来返回堆栈的大小。

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

这可能是一个好主意，添加self.top = None到__init__，虽然这不是绝对必要的。您可能希望将其标记为带有下划线的私人名称：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

破坏性堆栈迭代

微信关注