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: