Python 2.7でフリーリスト機能を持つスタックを実装する

Question

フリーリスト機能を持つスタックを設計します（ノードがポップされた後、そのスペースは将来のプッシュ操作で再利用可能で、空きリストに保持されます）。コードは単純化されていて、ある視点では意味をなさないので、以下のコードを使用してフリーリスト付きプロトタイプの一般的な考え方を示しています。

私の質問は、popの設計方法に関するものです。私の混乱はpopの操作の後にノードへの参照が返されたためです。例えば、node1 = stack.pop()というコードでは、ノードへの参照はpopを呼び出すクライアントによって使用され、同じノード参照は空きリストで再利用されますそのような競合を解決する方法と、スタック、リンクされたリストまたはキューを持つデザインフリーリスト機能の一般的なアドバイスについては疑問があります。

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

あなたは値を保持する代わりにStackNodeのpushに与えられたvalueを返すことによって、あなたのコードを簡素化することができます。結果を返す前にからNoneをpopに設定することができるので、メモリ消費の心配はありません。以下は、これが実際にどのように動作するかの簡単な例は次のとおりです。

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

出力：あなた `push`が値ではなく、ノードを受け入れるとき

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