破坏性堆栈迭代 [英] Destructive Stack Iteration

问题描述

这是我的堆栈实现.

类堆栈:def __init__(self):self.head = 无self.size = 0def push(self, item):节点 = 节点(项目)如果不是 self.head:self.head = 节点别的:node.next = self.headself.head = 节点self.size += 1def pop(self):如果 self.size == 0:raise ValueError('弹出一个空栈！')item = self.head.valself.head = self.head.next归还物品def peek(自我):如果 self.size == 0:raise ValueError('偷看一个空栈！')返回 self.head.valdef __iter__(self):回归自我def __next__(self):如果 self.head:curr = self.head别的:引发停止迭代()self.head = self.head.next返回当前值类节点:def __init__(self, val):self.val = valself.next = 无如果 __name__ == '__main__':堆栈 = 堆栈()堆栈推(12)堆栈推(13)堆栈推送(9)对于堆栈中的项目:打印(项目)打印(堆栈.偷看())

这个问题是迭代.迭代是破坏性的，因此在迭代结束时调用 peek 会引发错误.

返回 self.head.valAttributeError: 'NoneType' 对象没有属性 'val'如何使迭代具有非破坏性?

解决方案

一种简单的方法来执行此操作，为您的 Stack 提供一个可用于迭代的替代头.我还添加了一个 __len__ 方法来返回堆栈的大小.

类堆栈:def __init__(self):self.head = 无self.size = 0def __len__(self):返回 self.sizedef push(self, item):节点 = 节点(项目)如果不是 self.head:self.head = 节点别的:node.next = self.headself.head = 节点self.size += 1def pop(self):如果 self.size == 0:raise ValueError('弹出一个空栈！')item = self.head.valself.head = self.head.next归还物品def peek(自我):如果 self.size == 0:raise ValueError('偷看一个空栈！')返回 self.head.valdef __iter__(self):self.top = self.head回归自我def __next__(self):如果 self.top:curr = self.top别的:引发停止迭代()self.top = self.top.next返回当前值类节点:def __init__(self, val):self.val = valself.next = 无如果 __name__ == '__main__':堆栈 = 堆栈()堆栈推(12)堆栈推(13)堆栈推送(9)打印('大小'，len(堆栈))对于堆栈中的项目:打印(项目)打印(堆栈.偷看())堆栈推(42)打印('大小'，len(堆栈))对于堆栈中的项目:打印(项目)

输出

尺寸 3913129尺寸 44291312

将 self.top = None 添加到 __init__ 可能是个好主意，尽管这不是绝对必要的.您可能希望将其标记为带有前导下划线的私有名称:self._top.

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

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

def push(self, item):节点 = 节点(项目)如果 self.head:node.next = self.headself.head = 节点self.size += 1

This is my Stack implementation.

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())

The problem with this is the iteration. The iteration is destructive and thus the call to peek at the end of the iteration throws an error.

return self.head.val AttributeError: 'NoneType' object has no attribute 'val' How do I make the iteration non-desctructive?

解决方案

A simple way to do this to give your Stack an alternative head that it can use for iterating. I've also added a __len__ method tha returns the Stack's size.

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)

output

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

It's probably a Good Idea to add self.top = None to __init__, although it's not strictly necessary. And you may wish to mark it as a private name with a leading underscore: self._top.

As timgeb implies in the comments, this approach is a little fragile, since we can only perform one iteration at a time on the stack, since we only have a single self.top.

---

BTW, you can optimize that push method slightly:

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

这篇关于破坏性堆栈迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！