增加数组双端队列的大小

Question

在创建基于数组的双端队列时，我正在尝试使用 space 尽可能高效。因此，数组从大小 1 开始，如果在将新值推送到双端队列（两端）时数组不够大，我将调用一个名为 "grow" 的函数。然后我 mod 保存双端队列的前面和后面。这是我到目前为止所做的示例：

def __init__(self):
# capacity starts at 1; we will grow on demand.
  self.__capacity = 1
  self.__contents = [None] * self.__capacity
  self.__front = 1
  self.__back = 1
  self.__size = 1

def __grow(self):
  old_list = self.__contents
  walk = self.__front
  for k in range(self.__capacity):
    self.__contents[k] = old_list[walk]
    walk = (1 + walk) % len(old_list)
  self.__front = 0
  self.__capacity = self.__capacity * 2

def push_front(self, val):
  if self.__size == len(self.__contents):
    self.__grow(self.__capacity)
  self.__front = (self.__front - 1) % len(self.__contents)
  self.__contents[self.__front] = val
  self.__size += 1

当我调用 grow 方法时，我的问题就来了。我不断收到错误消息，指出我正在给 'grow' 两个位置参数，但我看不到发生的位置或方式。如果有人对如何改进它有任何想法，以便它只有一个位置参数？另外，我在 grow 方法中遍历重新索引的推理是否和我在 push front 方法中的推理一样有意义？

Answer 1

如果要向 __grow 传递参数，则需要向 __grow 添加一个参数，即：

def __grow(self, size):

目前它只有一个self参数，但是你在调用它的时候也会传入self.__capacity。但是，我认为您真的是想不带参数地调用 grow:

if self.__size == len(self.__contents):
  self.__grow()

Answer 2

class 中的所有实例方法都将调用实例作为它们的第一个参数，除非您使用 class 调用该方法，在这种情况下您必须提供一个实例作为第一个参数。

class A:
    def __init__(self):
        pass

    def f(self, x):
        print(self, x)

a = A()
a.f(1)    # <A object at 0x7fa9a067da90> 1
A.f(a, 2) # <A object at 0x7fa9a067da90> 2

所以当你调用 self.__grow(self.__capacity) 时，它会变成 Deque.__grow(self, self.__capacity)。但是你的 __grow 方法只需要 self.

增加数组双端队列的大小

increase the size of array deque

python-3.x

arraydeque