A user of a stack implementation expects a dynamic data structure. C does not provide that directly in language terms. You have to allocate and administrate the memory your own.
Allocating an array, therefore a static sized structure, is very easy. However, you have the problem, that the number of maximum entries is limited. If you make the array too small, this will cause errors, if you make the array very big, you are waisting memory.
A solution for this is to dynamically reallocate the array, if the number of entries exceeds the array size. But this moves the whole memory to another place in memory, what has some disadvantages. (I. e. you have to copy the whole memroy and it is not possible to hold a pointer to a specific entry.)
Having a linked list is the contrary. You (dynamically) allocate memory for each entry. You can free the memory for a single entry on removing from stack. This sounds better, but has the caveat, that you spent a pointer size of memory for each entry. Typically this is the size for an entry. So you double the memory consumption. Beside this, allocating small pieces of memory over and over wastes memory, too.
So you can implement a compromise: A linked list of arrays: You allocate a block for a number of entries, let’s say 256. Then you fill that block with entries, without reallocating or allocating memory. If the number of entries exceeds that value, you allocate a new block for additional 256 entries. The blocks are linked. So it is a linked list of arrays.
Esp. for a stack – you do not have removals in the middle of the structure – this is the best implementation in most cases.
2
solved Stack Implementations in C [closed]