Previously I have already implemented linked list based abstract data type Stack. As demanded by a friend of mine Romualdas, in this post I will implement dynamic array based Stack. According to Wikipedia, dynamic array is a random access, variable-size list data structure that allows elements to be added or removed. It is based on the idea of fixed array that can be extended (usually doubled) when the capacity is reached while storing the logical size or number of items in the array.

Dynamic array based implementation of stack has several advantages over linked list based:

• there is no need to store reference to the next element so memory usage is smaller
• memory is allocated / deallocated in chunks so memory pressure is lower

On the other hand, the cost of adding new items is higher for dynamic array based implementation due to array resizing. The good news is – it’s still constant time.

As you can see, when pushing we create new double size array if the original one is full. The really interesting part here is function pop: we are halving the size of array only when it’s ¼ full. Why not ½ full? Imagine sequence of actions:

• create new stack (array capacity – 1, items – 0)
• push item (array capacity – 1, items – 1)
• push item (array capacity – 2, items – 2) ← doubled
• pop item (array capacity – 1, items – 1) ← halved
• push item (array capacity – 2, items – 2) ← doubled
• pop item (array capacity – 1, items – 1) ← halved

By triggering shrinking when an array is ¼ full we amortize the cost of working at the boundaries.