Python 中的堆栈数据结构参考问题

Question

我正在尝试使用 findMin() 的附加方法构建堆栈 adt，该方法 return 是堆栈中的最小整数。我正在使用我在 python 中构建的 2 个堆栈来执行此操作（注意在此 class 之外，堆栈工作正常）。

from StackandQueueADT import Stack


class MinStack:
'This class has same functionality as a regular stack with 1 extra method that finds min of stack'
'it will use a min stack to keep track of min number'
def __init__(self):
    self.myStack = Stack()
    self.minStack=Stack()
    
def isEmpty(self)->bool:
    if(self.myStack.isEmpty()):
        return True
    return False

        
def push(self,x)-> None: 
    if(self.isEmpty() or x <= self.minStack.peek()):
            self.minStack.push(x) 
    self.myStack.push(x)


def pop(self)->int:
    if(not self.minStack.isEmpty() and self.myStack.peek() == self.minStack.peek()):
        print("what is happening with current stack Before?: " + str(self.myStack.peek()))
        print("pop minstack: " + str(self.minStack.pop()))
        print("what is happening with current stack After?: " + str(self.myStack.peek()))
    return self.myStack.pop()
def peek(self)->int:
    if(self.myStack.isEmpty()):
        return -1
    return self.myStack.peek()
def getMin(self)->int:
    if(self.minStack.isEmpty()):
        return -1
    return self.minStack.peek()

我遇到的问题出在 pop() 方法中。不知何故，如果它进入 if 语句从 minstack 中删除元素，它也会从 myStack 中删除元素。也就是说，它会在调用“return self.myStack.pop()”之前从 myStack 中删除元素。

我使用以下示例对此进行了测试：

minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print("pop: "  + str(minStack.pop()))

在这个例子中，当我只从 minStack 中弹出 -3 时，它隐式地从 minStack 和 myStack 中弹出。请注意，单独测试每个堆栈工作正常，但以某种方式这样做时，看起来相同的引用被传递给两个堆栈。

如果需要，这是我的堆栈 class:

class Stack:
stack=[]
top = -1

def isEmpty(self):
    if self.top==-1:
        return True
    return False
def push(self,data):
    self.top = self.top+1
    self.stack.insert(self.top,data)
def pop(self):
    if self.isEmpty():
        print("The stack is empty!,nothing to pop")
        return None
    value = self.stack[self.top]
    self.stack.pop(self.top)
    self.top = self.top-1
    return value
def peek(self):
    if self.isEmpty():
        print("The stack is empty!")
        return -1
    
    return self.stack[self.top]

Answer 1

class Stack:
    stack=[]

a = Stack()
b = Stack()

print("a's stack", a.stack) # a's stack []
a.stack.append(1)
print("b's stack", b.stack) # b's stack [1]

在python中，class下定义的变量是class级变量，在class的所有实例之间共享。在您的代码中 self.minStack 和 self.myStack 是不同的实例，但它们在 Stack class.

中共享相同的 stack 变量

当您通过 self.stack/top 访问时，它将为该实例创建独立的引用，但 stack 引用仍然引用同一个列表对象。你可能想做

class Stack:
    def __init__(self):
        self.stack = []
        self.top = -1

这是一个非常混乱且冗长的主题，因此我建议您阅读有关 class 变量的内容。

Python 中的堆栈数据结构参考问题

Stack DataStructure Reference Issue in Python

python

reference

stack

minimum