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: