添加元素到數組的頭部，同時從尾部刪除

我有一個恆定大小的數組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

添加元素到數組的頭部，同時從尾部刪除

回答

相關問題