什么C#数据结构支持以下？

Question

我需要一个C#数据结构,它以下列方式工作:

1. 使用静态大小定义它
2. 将新数据添加到列表末尾
3. 最旧的数据下降.
4. 随机访问数据元素

示例:如果我定义了5个元素的结构并添加了以下内容

1,2,3,4,5,6,7,8

数据结构如下所示:

4,5,6,7,8

我不确定哪种结构会以这种方式工作.向量？名单？堆？数据结构支持静态大小,如数组和推送数据,推送旧数据.

堆栈/队列不提供随机访问.列表没有"推"操作.

也许是LinkedList并为"push"添加自定义操作,删除第一个元素？LinkList随机访问是o(n)操作.

Answer 1

为了获得最大效率,这可能是实现循环缓冲区的自定义类.

只需在实例化时创建一个固定大小的数组来保存数据.此外,还有一个起始索引,一个大小成员和一个容量,因此您可以知道缓冲区中有多少数据以及它的起始位置.

因此,首先,您的列表不包含任何数据,起始位置为0,大小为0.

当你添加一个项目时,它会进入元素(start + size) % capacity,size如果还没有,则会递增capacity.如果是在capacity你增加start以及,缠绕如果需要的话:start = (start + 1) % capacity.

要从n列表中获取索引处的元素,您实际上是通过以下方式调整它start:

return element[(start + n) % capacity];

我没有介绍删除列表的开头,因为那不符合您的规范.但是,这是一个简单的检查,以确保size不是0,然后提取项目element[start],然后递增start与上面显示的相同的环绕.

在伪代码中(未经测试但应该接近):

def listNew (capacity):
    me = new object
    me.capacity = capacity
    me.data = new array[capacity]
    me.start = 0
    me.size = 0
    return me

def listAdd (me, item):
    if me.size = me.capacity:
        me.data[me.start] = item
        me.start = (me.start + 1) % me.capacity
    else:
        me.data[(me.start + me.size) % me.capacity] = item
        me.size = me.size + 1

def listGet (me, index):
    if index > size:
        return 0 # or raise error of some sort
    return me.data[(me.start + index) % me.capacity]

def listRemove (me):
    if size == 0:
        return 0 # or raise error of some sort
    item = me.data[(me.start + index) % me.capacity]
    me.start = (me.start + 1) % me.capacity
    me.size = me.size - 1
    return item

根据要求,所有这些操作都是O(1)时间复杂度.

对于添加数字你具体的例子1,通过8对五元素列表中,你最终会得到:

  0   1   2   3   4 <--- index
+---+---+---+---+---+
| 6 | 7 | 8 | 4 | 5 |
+---+---+---+---+---+
              ^
              +--------- start    = 3
                         size     = 5
                         capacity = 5

这样,从缓冲区中提取虚拟索引3(第四个数字)将为您提供实际索引:

  (start + 3) % capacity
= (  3   + 3) %    5
=       6     %    5
=             1