Implementieren von Stack mit Freelist-Funktion in Python 2.7

Question

Entwerfen Sie einen Stapel mit Frei-List-Feature (d. H., Nachdem ein Knoten platzt, dessen Speicherplatz durch zukünftige Push-Operation wiederverwendbar ist und in der freien Liste gespeichert wird). Der Code ist vereinfacht und macht in gewisser Hinsicht keinen Sinn, und ich benutze nur den folgenden Code, um die allgemeine Idee von Stack mit freier Liste (als Prototyp) zu zeigen.

Meine Frage ist, wie man pop Operation entwerfen. Meine Verwirrung ist, da ein Verweis auf einen Knoten nach pop Operation zurückgegeben wird, zum Beispiel in meinem Code gibt es node1 = stack.pop(), der Verweis auf einen Knoten könnte von Client verwendet werden, der pop aufrufen, und der gleiche Knoten Verweis wird in der freien Liste und möglicherweise zurückgefordert von anderen push Operation verwendet werden, wie Sie solche Konflikte lösen und Fragen für allgemeine Hinweise für Design-freie Liste Feature mit Stack, verknüpfte Liste oder Warteschlange.

MAXSIZE = 100 
freeListHead = None 

class StackNode: 
    def __init__(self, value, nextNode): 
     self.value = value 
     self.nextNode = nextNode 
class Stack: 
    def __init__(self): 
     self.top = None 
     self.size = 0 
    def peek(self): 
     # return StackNode 
     return self.top 
    def push(self, value): 
     global freeListHead 
     if self.size >= MAXSIZE: 
      raise Exception('stack full') 
     node = freeListHead 
     node.value = value 
     freeListHead = node.nextNode 
     node.nextNode = self.top 
     self.top = node 
     self.size += 1 
    def pop(self): 
     if self.size == 0: 
      return None 
     node = self.top 
     self.top = self.top.nextNode 
     self.size -= 1 
     return node 

if __name__ == "__main__": 
    # initialization for nodes and link them to be a free list 
    nodes = [StackNode(-1, None) for i in range(MAXSIZE)] 
    freeListHead = nodes[0] 
    for i in range(0, len(nodes)-1): 
     nodes[i].nextNode = nodes[i+1] 
    stack = Stack() 
    stack.push(1) 
    stack.push(50) 
    stack.push(100) 
    stack.push(200) 
    print stack.peek().value 
    node1 = stack.pop() 
    print node1.value 
    print stack.peek().value 

Answer 1

Sie könnten Ihren Code vereinfachen, indem die value zu push statt StackNode gegeben Rückgabe des Werts zu halten. Es gibt keine Bedenken hinsichtlich des Speicherverbrauchs, da Sie node.value auf None in pop setzen können, bevor Sie das Ergebnis zurückgeben. Im Folgenden finden Sie einfaches Beispiel, wie dies in der Praxis funktionieren würde:

class Node: 
    def __init__(self): 
     self.nextNode = self.value = None 

class Stack: 
    def __init__(self, maxSize): 
     self.maxSize = maxSize 
     self.size = 0 
     self.top = self.free = None 

    def push(self, value): 
     if self.size == self.maxSize: 
      raise Exception('Stack full') 

     if self.free: 
      node = self.free 
      self.free = node.next 
     else: 
      node = Node() 

     node.value = value 
     node.nextNode = self.top 
     self.top = node 
     self.size += 1 

    def pop(self): 
     if not self.top: 
      raise Exception('Stack empty'); 
     node = self.top 
     self.top = node.nextNode 
     node.nextNode = self.free 
     self.free = node 
     self.size -= 1 
     result = node.value 
     node.value = None 

     return result 

stack = Stack(3) 
for i in range(3): 
    stack.push(list(range(i + 1))) 

while stack.size: 
    print(stack.pop()) 

Ausgang:

[0, 1, 2] 
[0, 1] 
[0]