1

Pythonで汎用スタックを作成するには? Pythonでの私のスタック実装:

class Node(object):
    def __init__(self, d):
        self.data = d
        self.nextNode = None

class Stack(object):
    def __init__(self):
        self.top = None

    def push(self, item):
        newNode = Node(item)
        newNode.nextNode = self.top
        self.top = newNode

    def pop(self):
        if self.top == None:
            return None
        item = self.top.data
        self.top = self.top.nextNode
        return item

今、私は Node クラスのオブジェクトを配置していますが、そこに何でも配置できるようにジェネリック Stack を実装する方法を教えてください。たとえば、新しいタイプのノードを作成したい場合

class NodeWithMin:
    def __init__(self, value, minval):
        self.data = value
        self.minval = minval

そして、これらのタイプのノードに基づいてスタックを作成できるため、次のようになります (もちろん機能しません)。

class StackWithMin(qs.Stack):
    def push(self, val):
        if self.peek() != None:
            minval = min(self.peek().value, val)
        else:
            minval = val
        qs.Stack.push(NodeWithMinV2(val, minval))

何か案が？

編集:次のエラーがあるため、機能しませんでした:

unbound method push() must be called with Stack instance as first argument (got NodeWithMinV2 instance instead)

私は逃したself

4

1 に答える 1

2

リストを使用することもできますが、より抽象化されたものが必要になることは完全に理解できます。

コレクション モジュールで両端キューを使用することもできます。両端から追加または削除でき、リストよりも抽象化されています。

あなたが持っているものは良さそうです。最小限のものを入れたい場合は、新しいクラスを作成し、そのインスタンスをプッシュ メソッドに item 引数として渡します。

私はここでちょっと推測していますが、あなたが望むのが優先キューであり、プッシュ年代順によって特定の端にあるものだけでなく、最も価値の低いノードをポップできる場合は、heapq モジュールをチェックアウトできます。それもひどく抽象化されているわけではありませんが、機能し、高速であり、自分で抽象化することを妨げるものは何もありません.

于 2012-08-24T22:53:34.693 に答える