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.

In this post I will implement another very popular abstract data type – Queue. Queue is a collection where the first element added to the structure must be the first one to be removed (or FIFO, First-In First-Out, for short). It is widely used in hardware and software for buffering and prioritization. Typically queue is implemented using (doubly) linked list or in some cases using dynamic arrays.

Usually linked lists have following functions:

• enqueue() – to add new element
• dequeue() – to remove last element and return its value
• peak() – to return value of the last element without removing it
• isEmpty() - to check whether the queue is empty or not
• length() – to get the number of items in the queue

Based on the previously described linked list, implementation of the queue is rather trivial:

In this post I will implement very popular abstract data type – Stack. Stack is a collection where the last element added to the structure must be the first one to be removed (or LIFO, Last-In First-Out, for short). It is widely used in hardware including CPU registers. In software it is used for memory allocation, to track active sub-routines (call stack) or to implement parsers and various higher-level algorithms. Typically stack is implemented using linked list or in some cases using dynamic arrays.

Usually stack has following functions:

• push() – to add new element
• pop() – to remove first element and return its value
• peek() – to return value of the first element without removing it
• isEmpty() - to check whether the stack is empty or not
• length() - to get the number of items in the stack

Based on the previously described linked list, implementation of the stack is rather trivial: