Circular Queue

Circular Queues are an abstract data structure. They are like normal queues, except that the end of the queue is attached to the beginning of the queue.

How does the Circular Queue work?

One of the important ways in which circular queues differ from normal queues is that the “front” and “rear” of the queue keep shifting as you enQueue and deQueue elements from the queue. In most cases, Circular Queues are implemented using Linked Lists which allow changing the pointer to “front” and “rear” elements.

How do you add an element to the Circular Queue?

You find out the rear element. If there is an empty space beyond the rear element, then we add the element behind the rear and move the pointer of rear to the new element.

If the circular queue is full then an error has to be produced stating that there is no space to insert another element.

It is worth noting that if the queue is implemented using Linked Lists, there is a fair chance that you can still create a new element and attach it to the queue’s rear end. In such a case, the size/capacity of queue keeps increasing as new elements are added to the queue.

How do you remove an element from the Circular Queue?

You find out the front element. You return the element at the front and move the pointer of front element to the next element.

If there are no elements present, you can return an error (or a null value) and set the pointers of both front and rear elements to a null value.

Rules of the Circular Queue

The Circular Queue has two operations:

  1. Get the first element: Use the front pointer to get the first element. If the element has to be fetched and removed from the queue, then this action is called popping the element.
  2. Get the last element: Use the rear pointer to get the last element.
  3. Add a new element to the Queue: Add a new element ahead of the first element and move the first element’s pointer to the new element.
  4. Remove an element from the Queue: Remove the element at the rear location and move the pointer for the last element to the one before it.

Like a normal queue, you are not allowed to add/remove an element which is not at either the front or rear position.

Usage

Circular Queues are used for processing elements in a round-robin fashion. It is particularly useful in task scheduling wherein once a task is completed, the processing system can process the next one in the queue. While the processing system is campleting tasks and removing them from the front, new tasks can be accepted and put at the rear.

Updated: