c - 在c中实现堆栈

Question

我想让堆栈与动态内存分配一起使用，但我需要知道哪个更有效：
例如，初始大小为 10，然后如果需要更多，我将其加倍。
或者我可以有一个初始大小 = 1 并为每个新输入添加一个位置。！？！

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

Answer 1

在需要时加倍效率更高。

如果您为每个 push 操作分配一个新数组，那么您所做的工作量与堆栈元素数量的平方成正比（当您 push element 时N+1，您必须将先前的N元素复制到新数组中）。

如果您在需要时将数组加倍，那么您所做的副本数与 N 的对数成正比，并且对于任何非平凡大小的堆栈，如您所知，这要小得多。

Answer 2

这是一个破碎的问题。哪个“更有效”完全取决于您的域。如果你有很多长度为 3 和 4 的堆栈，那么预先分配 10 并随后休眠 5 年将比从 1 开始并加倍更快。如果你有很多长度为 1 的堆栈，那么分配 10 是一种浪费。

当然，当我说“浪费”时，我的意思是浪费了宝贵的几纳秒，你将永远无法回来。假设您使用的是“普通”计算机并且没有在 Conway 的生命游戏中实现 C 或任何不寻常的东西，在这种情况下，这些分配可能很重要。因此，对其进行分析并找出答案。

如果你想要一些简单且更有可能有效的东西，那么先分配 10 个，然后在需要时加倍。

Answer 3

这取决于。通常加倍会更有效，但这种方法会浪费大量空间（多达一半的分配空间未使用）。您的逐一增加方法没有这个缺点。但是，每次添加时都必须复制整个数组确实效率低下。因此，如果空间效率是您最关心的问题，您最好将堆栈表示为链表。

Answer 4

必要时将堆栈大小加倍的摊销成本比初始化为 1 低很多。所以是的，加倍更好。话虽如此，我也会推荐一个适当的删除方案。当当前堆栈的 1/4 正在使用时，类似于释放一半堆栈的东西。以这种方式，边缘加法和减法不会破坏效率。