在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时，沿着释放堆栈的一半的某些东西。以这种方式，边缘添加和减少不会破坏效率。