c - 在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 的对数成正比，并且对于任何非平凡大小的堆栈，这要小得多，如您所知。