固定大小的有序数据结构和pop/push同时操作

Question

对于这种需求，您推荐使用哪种python数据结构：

• 在init定义的固定大小
• 有序数据
• 在结构的开头添加数据，删除其末尾的数据(作为队列结构)
• 在开头添加数据，返回结束时的数据
• 任何数据都可以访问，但不能删除。
• 结构可以清洗

我看上去像清单一样的结构，但它并没有提供我想要的。dequeue看起来很棒，但我不需要在两边添加或删除元素。

我想要这样的东西：

last_object = my_struct.add(new_first_object)

有什么想法吗？

Answer 1

使用collections.deque初始化的maxlen正是您所需要的，它可以在O(1)中执行所需的操作，并处理“在结束时删除”：

如果maxlen未指定或不指定，则deques可能增长到任意长度。否则，deque将被限制到指定的最大长度。一旦一个有界长度deque是满的，当添加新的项目时，相应数量的项目从另一端被丢弃。

只需使用.append而不使用其他任何东西。

根据文档，它还支持O(1)中的“窥视”或-1 (对于“在开头添加数据，在其结束时返回数据”的要求)

如果您真的不希望类中存在任何其他方法(例如，IDE不会自动完成add以外的其他东西)，您可以将deque包装在您自己的自定义类中，这个类只有一个调用deque's append的add方法。

示例：

from collections import deque

class MyCollection:
    def __init__(self, maxlen):
        self.d = deque(maxlen=maxlen)

    def add(self, new_first_object):
        result = None if len(self.d)==0 else self.d[0]
        self.d.append(new_first_object)
        return result

my_struct = MyCollection(3)
my_struct.add(1)
my_struct.add(2)
my_struct.add(3) # my_struct is now full
print(my_struct.add(4))
print(my_struct.add(5))
print(my_struct.add(6))

输出：

1
2
3