Circular Queue

A Circular Queue is queue following “First In First Out” (FIFO) principle with the difference that the last element is associated back with the first element of the queue.

Insertion will be done at end called the REAR. Deletion will take place at beginning called the REAR. The elements that are inserted earlier will be deleted first. The elements added later will be deleted later. An item is added at the end and removed from the beginning and the first follows the last element.  It is used to maintain sequence of events in a round robin fashion.  Just like pass  the parcel  game.

Circular Queue is used in problems where you have to maintain the first come first serve sequence of tasks in such a way that after the last task you need to go back to the first one. 

In real world you can see circular queue in the form of luggage carousal in airports where the travellers collect their luggage after a flight. Manufacturing units with assembly line for assembling products is another example of circular queue in real life. You have climbed on escalators. This is another example of this kind of queue.

Memory Representation of Circular Queue

Circular Queues can also be represented in memory in two ways.

• Using the contiguous memory like an array
• Using the non-contiguous memory like a linked list

Circular Queue using an Array

In this representation this Queue is implemented using the array. Variables used in this case are

• QUEUE- the name of the array storing queue elements.
• MAX- defining that how many elements (maximum count) can be stored in the array representing the queue.
• FRONT- the index where the first element is stored in the array representing the queue. If the last element is deleted from index MAX, then the FRONT variable is updated with 0 (first index of the array).
• REAR- the index where the last element is stored in array representing the queue. If last stored value is at MAX and FRONT is not 0 then the new element will be stored at 0 index.

Using Linked List

In this representation the circular queue is implemented using a Linked List. Using linked list for creating a queue makes it flexible in terms of access.

Pointers (links) to store addresses of nodes for defining a circular queue are

• FRONT- address of the first element of the Linked list storing the Queue.
• REAR- address of the last element of the Linked list storing the Queue. LINK part of the REAR node stores the address of the first node.

Circular Queue Applications

These Queues are used in various applications in Computer Science-

• Round robin execution of Jobs in a multi programming OS.
• Looped execution of the slides of a presentation.
• Assigning turns to play for multiplayer gaming systems
• Process management tasks by Operating System.
• Browsing through the open windows applications using alt+tab(Microsoft Windows)
• Time division multiplexing in case of Networks and Communications.

admin