Linear Queue
It is a linear data structure that works on the principle of FIFO (First in First out) i.e. the element which is enqueued first will be dequeued first. There is one criteria i.e. element is always added in the rear part or the end part of the queue and always deleted from the front part of the queue. The enqueue operation takes place on the rear end whereas dequeue operation takes place on the front end. Insertion of elements from the rear end in the queue is known as enqueue operation and deletion of elements from the front end of the queue is known as dequeue operation. In this queue, the rear end always lies after the front end of the queue.
Circular Queue
It is also a linear data structure that works on the principle of FIFO (First in First out). In this type of queue element can be added in any position or can be deleted from any position in the array but we have to maintain the pointers which will point towards the front and rear end of the queue. In this queue, the rear end can be at any point in the array.
Given below is the example that will help to understand how Circular Queue is better than Linear Queue:
-
When Enqueue operation is performed on both types of queues:
Let the queue is of size 6 having elements {5, 10, 15, 20, 25, 30}. In both the queues the front points at the first element 5 and the rear points at the last element 30 as shown in the below image:
-
When the dequeue operation is performed on both the queues:
Consider the first 2 elements that are deleted from both the queues. In both the queues the front points at the element with value 15 and the rear points at the element with value 30 as shown in the below image:
-
Now again enqueue operation is performed:
Consider an element with a value of 35 is inserted in both the queues. The insertion of element 35 is not possible in Linear Queue but in the Circular Queue, the element with a value of 35 is possible as shown in the below image:
Explanation:
- The insertion in the queue is done from the rear end and in case of Linear Queue of fixed size insertion is not possible when rear reaches the end of the queue.
- But in the Circular Queue, the rear end moves from the last position to the front position circularly.
Circular queue is more efficient than a linear queue due to following reasons:
-
Efficient utilization of memory: Circular queue is famous for its memory utilization process. There is no wastage of memory as it uses the unoccupied space, and memory is used properly in a valuable and effective manner in comparison to the linear queue.
-
Easier for insertion-deletion: In the circular queue, if the queue is not fully occupied, then the elements can be inserted easily on the vacant locations. But in the case of a linear queue, insertion is not possible once the rear pointer reaches the last index even if there are empty locations present in the queue.
-
Ease of performing operations: In the case of linear queue, FIFo is followed, i.e. the element which is inserted first will be removed first from the queue. But this is not the scenaria in the case of a circular queue as the rear and front end are not fixed so the order of insertion-deletion can be changed, which is very useful.
This article tried to discuss the Advantages of Circular Queue over Linear Queue with the help of examples. Hope this blog helps you understand the concept. To learn more feel free to check Foundation Courses at Prepbytes