多个堆栈代码不会增加堆栈号

Question

这是我自己在 Python 中实现的 SetOfStacks 问题 (CTCI 3.3)。简单地说，我想将堆栈的大小限制为 10。因此，当我尝试推送超过容量的内容时，我会再生成一个堆栈，让用户继续推送新元素。我试图将其表示为 collections.defaultdict(list) 数据结构。为了跟踪正在使用的堆栈号，我创建了一个名为 current_stack 的变量。然而，即使在容量过剩的情况下（请参阅##### 标记处的设计），似乎 current_stack 确实 而不是 按预期增加。我的代码有什么问题？ self.current_stack 不会像对象中的全局变量一样工作吗？

class SetOfStacks():
    def __init__(self, stacksize):
        self.size = stacksize  # const
        self.c = collections.defaultdict(list)
        self.current_stack = 0  # self.c[self.current_stack]

    def push(self, e):
        if len(c[self.current_stack]) + 1 > self.size: #####
            self.current_stack += 1
        self.c[self.current_stack].append(e)

    def pop(self):
        if self.current_stack > 0 and len(c[self.current_stack]) == 1 :
            popped = self.c[self.current_stack].pop()
            self.current_stack -= 1
            return popped
        elif self.current_stack == 0 and len(c[self.current_stack]) == 0:
            raise IndexError("No more elements to pop.")
        else:
            return self.c[self.current_stack].pop()

    def __repr__(self):
        return print(self.c)

st = SetOfStacks(10)
for i in range(21):
    st.push(i)
st

结果：

defaultdict(<class 'list'>, {0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]})

Answer 1

您在 push() 的 len() 调用中缺少 self：

def push(self, e):
    if len(c[self.current_stack]) + 1 > self.size: #####
           ^

你需要：

def push(self, e):
    if len(self.c[self.current_stack]) + 1 > self.size: #####

您所引用的环境中必须有另一个 c，它永远不会被添加到 - 因此大小始终相同。

并且 pop() 中有几个类似的错误，例如：

def pop(self):
    if self.current_stack > 0 and len(c[self.current_stack]) == 1 :
                                      ^

注意：def __repr__():应该return一个str实际上不是print()，例如：

def __repr__(self):
    return repr(self.c)

通过这些修复，您将获得预期的输出：

defaultdict(<class 'list'>, {0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
                             1: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
                             2: [20]})

多个堆栈代码不会增加堆栈号

Multiple stack code does not increment the stack number

python

collections

stack

defaultdict