Destruktive Stack-Iteration

Question

Dies ist meine Stack-Implementierung.

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

Das Problem dabei ist die Iteration. Die Iteration ist destruktiv, und daher ruft der Aufruf am Ende der Iteration einen Fehler hervor.

return self.head.val AttributeError: 'NoneType' object has no attribute 'val' Wie mache ich die Iteration nicht-destruktiv?

Answer 1

Ein einfacher Weg, dies zu tun um deinem Stack einen alternativen Kopf zu geben kann zum Iterieren verwenden. Ich habe auch eine __len__ Methode hinzugefügt, die die Größe des Stapels zurückgibt.

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) 

Ausgang

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

Es ist wahrscheinlich eine gute Idee self.top = None-__init__ hinzuzufügen, auch wenn es nicht unbedingt notwendig ist. Und Sie können es als einen privaten Namen mit einem führenden Unterstrich markieren: self._top.

Wie Timgeb impliziert in den Kommentaren, ist dieser Ansatz ein wenig zerbrechlich, da wir nur eine Iteration zu einer Zeit auf dem Stapel ausführen können, da wir nur eine einzige self.top haben.

---

BTW, können Sie diese push Methode leicht optimieren:

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

Answer 2

Weil Sie mehr als ein Iterator auf demselben Stapel haben kann, hat __iter__ ein Iterator-Objekt zurück, das den Stapel iteriert:

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 

Answer 3

Das Problem ist, dass Sie keinen Unterschied zwischen dem machen iterable Stack selbst und die Iterator, die __iter__ sollte zurückgeben. __next__ sollte auf dem Iterator aufgerufen werden, nicht auf der Stack selbst.

Ich schlage vor, die folgende Lösung:

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 

Lassen Sie sich in Stack von __next__ los und stellen Sie __iter__ an:

def __iter__(self): 
    return StackIterator(self) 

Demo:

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