在c中實現堆棧

Question

我想使堆棧與動態內存分配一起工作，但我需要知道它更高效：
初始大小例如爲10，然後如果我將其加倍需要更多。
或者我可以有一個初始大小= 1，併爲每個新的輸入添加一個地方。 ！？！

int *tmp = malloc(sizeof(int) * 2 * dm->capacity); \* dm->capacity = 10 *\ 
int *tmp = malloc(sizeof(int)); 

Answer 1

在需要時增加一倍的方式更有效。

如果分配用於每個按壓操作一個新的數組，則做工作的正比於（堆元件的數量的平方當你推元件N+1，則必須複製先前N元素到的量新陣列）。如你所知，如果你在需要的時候加倍數組，那麼你所做的拷貝數與N的對數成正比，對於任何非平凡大小的堆棧，這是相當小的。

Answer 2

這是一個問題。哪種「更高效」完全取決於您的域名。如果你有很多長度爲3和4的堆棧，那麼先分配10個，然後再睡5年會比從1開始加倍並且加倍。如果你有很多長度爲1的堆棧，那麼分配10是很浪費的。

當然，當我說「浪費」時，我的意思是浪費幾個寶貴的納秒，你永遠無法找回來。假設你使用的是「普通」計算機，並且沒有在Conway的生命遊戲中實施C或任何不尋常的事情，在這種情況下，這些分配可能很重要。所以，簡介並找出答案。

如果您想要一些簡單而且更有效的方法，那麼先分配10個，然後在需要時再分配10個。

Answer 3

這取決於。通常情況下，加倍效率會更高，但這種方法會浪費很大的空間（多達一半的空間未被使用）。您的擴充方案沒有這個缺點。但是，在每次添加時都需要複製整個數組是非常低效的。因此，如果空間效率是您最關心的問題，那麼您最好將堆棧表示爲鏈接列表。

Answer 4

需要時將堆棧大小加倍的分攤成本比初始化爲1要低很多。所以是的，加倍會更好。話雖如此，我還建議一個適當的刪除方案。當使用當前堆棧的1/4時，沿着釋放堆棧的一半的某些東西。以這種方式，邊緣添加和減少不會破壞效率。