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 参数传递到您的 push 方法中。

我在这里有点猜测，但是如果您想要的是优先级队列，您可以在其中弹出价值最小的节点，而不仅仅是通过推送年表来弹出给定端的东西，您可以查看 heapq 模块。它也不是非常抽象，但它可以工作，而且速度很快，没有什么可以阻止你自己更好地抽象它。

于 2012-08-24T22:53:34.693 回答