DataStructures Series #6 – The Queue ADT

Originally posted on my medium page: https://medium.com/@otarutunde

The Queue ADT

The queue allows operations at both ends unlike the stack that allows operations only at one end. The insertion is performed at a position called the ‘rear’ and the deletion operation is performed at a position called the ‘front’. The operations in a queue are performed based on the FIFO (First in First out) principle.

The Queue

Queue Operations:

  • EnQueue Element
  • DeQueue Element
  • Peek Element

EnQueue — This would insert an element at the rear of the queue.

DeQueue — This would remove an element at the front of the queue.

Peek — This would fetch and not remove an element at the front of the queue.

Implementation

One way to implement the Queue ADT is to use an array.

Below is a pseudocode implementation:

Initialise new array {random size}

set currentRearIndex = 0;

enQueue(element) : set array[currentRearIndex] = element;
                   currentRearIndex++;

deQueue() : if (currentRearIndex == 0)
               return null;
            otherwise
               value = array[0];

            // shift elements to the right in array
            for all elements in array starting from index 0
               // e is the current elementIndex in array
               set array[e]  = array[e + 1];
            
            set array[currentRearIndex - 1] = NULL;
            currentRearIndex--;
             
            return value;

peek() : if (currentRearIndex == 0)
            return null;
         otherwise:
            return array[0];

This implementation is inefficient as we can see, we have to move all elements by a place after every deQueue operation, imagine we had 1 million elements in the array, the computer would have to perform around a million operations just to remove one element. Another bottleneck we would have is if the queue gets filled up, we would have to create a bigger array and transfer all the data from the old one to the new one, this too can be very expensive if we have many elements to transfer hence why the array is not ideally the best data structure to use in implementing a queue.

Real life Applications

  • Operating Systems Job Scheduling— Queues are used in your Operating system for task scheduling
  • Customer Service call management — When you call a customer service and you are told to wait, your call is actually in a queue.

REFERENCES: