Linear vs Circular Queue
What is a Linear Queue?
A linear queue is a linear data structure that serves the request first, which has been arrived first. It consists of data elements which are connected in a linear fashion. It has two pointers, i.e., front and rear, where the insertion takes place from the front end, and deletion occurs from the front end.
Operations on Linear Queue
There are two operations that can be performed on a linear queue:
- Enqueue: The enqueue operation inserts the new element from the rear end.
- Dequeue: The dequeue operation is used to delete the existing element from the front end of the queue.
What is a Circular Queue?
As we know that in a queue, the front pointer points to the first element while the rear pointer points to the last element of the queue. The problem that arises with the linear queue is that if some empty cells occur at the beginning of the queue then we cannot insert new element at the empty space as the rear cannot be further incremented.
A circular queue is also a linear data structure like a normal queue that follows the FIFO principle but it does not end the queue; it connects the last position of the queue to the first position of the queue. If we want to insert new elements at the beginning of the queue, we can insert it using the circular queue data structure.
In the circular queue, when the rear reaches the end of the queue, then rear is reset to zero. It helps in refilling all the free spaces. The problem of managing the circular queue is overcome if the first position of the queue comes after the last position of the queue.
Conditions for the queue to be a circular queue
- Front ==0 and rear=n-1
- Front=rear+1
If either of the above conditions is satisfied means that the queue is a circular queue.
Operations on Circular Queue
The following are the two operations that can be performed on a circular queue are:
- Enqueue: It inserts an element in a queue. The given below are the scenarios that can be considered while inserting an element:
- If the queue is empty, then the front and rear are set to 0 to insert a new element.
- If queue is not empty, then the value of the rear gets incremented.
- If queue is not empty and rear is equal to n-1, then rear is set to 0.
- Dequeue: It performs a deletion operation in the Queue. The following are the points or cases that can be considered while deleting an element:
- If there is only one element in a queue, after the dequeue operation is performed on the queue, the queue will become empty. In this case, the front and rear values are set to -1.
- If the value of the front is equal to n-1, after the dequeue operation is performed, the value of the front variable is set to 0.
- If either of the above conditions is not fulfilled, then the front value is incremented.
Differences between linear Queue and Circular Queue
| Basis of comparison | Linear Queue | Circular Queue |
|---|---|---|
| Meaning | The linear queue is a type of linear data structure that contains the elements in a sequential manner. | The circular queue is also a linear data structure in which the last element of the Queue is connected to the first element, thus creating a circle. |
| Insertion and Deletion | In linear queue, insertion is done from the rear end, and deletion is done from the front end. | In circular queue, the insertion and deletion can take place from any end. |
| Memory space | The memory space occupied by the linear queue is more than the circular queue. | It requires less memory as compared to linear queue. |
| Memory utilization | The usage of memory is inefficient. | The memory can be more efficiently utilized. |
| Order of execution | It follows the FIFO principle in order to perform the tasks. | It has no specific order for execution. |