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: