I want to make stack which work with dynamic memory allocation, but I need to know about which it is more efficient :
to have an initial size like 10 for example , and then I double it if I need more.
or I can have an initial size = 1 and for every new input adding one place . !?!
int *tmp = malloc(sizeof(int) * 2 * dm->capacity); \* dm->capacity = 10 *\
int *tmp = malloc(sizeof(int));
Doubling when needed is way more efficient.
If you allocate a new array for every push operation, then you do an amount of work proportional to the square of the number of stack elements (when you push element N+1, you must copy the previous N elements to the new array).
If you double the array when needed, then the number of copies you do is proportional to the logarithm of N, and for any nontrivial size stack, that's substantially smaller, as you know.
It's a broken question. Which is "more efficient" completely depends on your domain. If you have a lot of stacks of lengths 3 and 4 then allocating 10 up front and subsequently sleeping for 5 years will be faster than starting with 1 and doubling. If you have a lot of stacks of length 1 then it's a waste to allocate 10.
Of course when I say "waste" I mean waste of a few precious nanoseconds you'll never be able to get back. Assuming you're on a "normal" computer and aren't implementing C in Conway's Game of Life or anything unusual, in which case these allocs might matter. So, profile it and find out.
If you want something simple and more likely effective than not, then allocate 10 up front and double when needed thereafter.
It depends. Usually doubling is going to be more efficient, but that approach can waste significant space (up to half the allocated space is unused). Your augment-by-one approach doesn't have that drawback. However it's really inefficient to have to copy the whole array on each addition. So if space efficiency were your primary concern, you may be better off representing your stack as a linked list.
The amortized cost of doubling the stack size when necessary is a lot lower than initializing to 1. So yes, doubling is better. That being said, I would also recommend a proper deletion scheme. Something along the lines of freeing half the stack when 1/4 of the current stack is in use. In this manner, edge additions and subtractions aren't wrecking the efficiency.
