添加元素到数组的头部，同时从尾部删除

我有一个恒定大小的数组x（通常大约100-200个条目），并且希望将常数较小的数组y（通常在2-10个条目之间）添加到头部，而在最后去除相同的大小。例如：添加元素到数组的头部，同时从尾部删除

缓冲液： X = [6 5 4 3 2 1]

新阵列在前面加： Y = [8 7]

所得缓冲液： X = [8 7 6 5 4 3]

等等...

注：我需要使用一个常规的C阵列和需要能够访问整个阵列，不仅头部或尾部。该数组非常小，但该函数经常被调用，所以我正在寻找一种不需要任何过多内存任务的解决方案。数组x和y在每一步中总是具有相同的大小。

这是一个缓冲区，循环/环形缓冲区，队列还是FIFO？我真的不知道这个应用程序的正确搜索词是什么。

语言为C.

来源

2015-12-14 DayAndNight

听起来像你描述的循环缓冲区。搜索了！ – Brian

与其移动大量数据，不如使用环形缓冲区并覆盖过时的元素。 –

[队列使用数组]可能重复（http://stackoverflow.com/questions/25346192/queue-using-arrays） – djechlin

如果你需要对数组内容线性访问，并希望不执行经常memcpy操作，这个可能的解决方案是一个flip缓冲或滑动缓存。

翻转缓冲区是数组需要的两倍（或者更多，如果你喜欢的话），这样你可以在没有任何环绕的情况下添加到末尾时移动尾指针，保持数据线性。

当您达到底层缓冲区的硬限制时，则执行滑动操作：将数组的上半部分移到下半部分，并从所有索引中减去相同的增量。

当这种滑动操作发生，你知道，所有数据和指标都在上隔断了，因为缓冲区，这是2 * N，宽从未包含超过N项：它是模拟的N大小的环形缓冲区。也就是说，从来没有出现过尾部撞到缓冲区末端的情况，但头部仍然位于较低分区（有超过N项）。

既然你想添加到前面，我们通过填充上分区开始，我们在向上翻转：

[x x x x x x | 6 5 4 3 2 1 ] -- six-element queue, twelve el. buffer 
      H    T 

Add 8 7, remove 2 1: 

[x x x x 8 7 | 6 5 4 3 x x ] 
     H    T 

Add 2 1 0 9, remove 6 5 4 3: 

[2 1 0 9 8 7 | x x x x x x ] 
H   T

头已达到-1！翻转到上隔断与memcpy，加6到头部和尾部：

[x x x x x x | 2 1 0 9 8 7 ] 
      H    T

注意，因为这两个分区不重叠，我们没有使用memmove：我们可以使用memcpy。

来源

2015-12-14 23:06:39 Kaz

您需要的是索引偏移量。所以，每次“插入”值时，只需将它们写入虚拟尾部，并更新索引偏移。这就是循环缓冲区的工作原理。

来源

2015-12-14 21:55:24

那么从<string.h>使用memmove()来移动数组的切片呢？如果没有真正衡量业绩，这不是排除的事情。任何使用链接列表的解决方案都可能涉及比高度优化的操作花费更长时间（即编译器甚至可能内联）。

这实际上取决于

元件的数量阵列中
元素类型
操作
所花费的时间修改相对于所述阵列的频率的大小一切

来源

2015-12-14 21:58:17 Jens

对于小型数据集，没有太多的插入，这通常比甚至用的memmove别的更快。 – Matt

这是重复的。以下是代码审查https://codereview.stackexchange.com/questions/64258/array-implementation-of-queue上的Java实现以及C中的其中一个问题Queue using Arrays。

来源

2015-12-14 21:59:20 djechlin

添加元素到数组的头部，同时从尾部删除

回答

相关问题