Linear vs Circular Queue: Data Structure
Difference Between Linear and Circular Queue
What is Linear Queue?
A linear queue is linear data structure which works on first in first out principle. We can say a linear queue is homogeneous collection of data items where new data items are added at one end of queue called rear and the deletion of the data item is done from other end called front of the queue.
There are two basic operations can be performed on queue
- Insert the data item into the queue called enqueue operation.
- Delete the data item from the queue called dequeue operation.
What is Circular Queue?
Circular Queue is special type queue, which follows First in First Out (FIFO) principle and as well as instead of ending queue at the last position, it starts again from the first position after the last position and behaves like circular linear data structure.
We can say it is extension of the queue data structure such that last element of the queue is associated with the first element of the queue and it is also referred as Circular Buffer. If we talk about normal queue, no additional element can be added if queue is full. Also, we can’t add the element in the queue if space is left in front of queue. So, to overcome this problem, Circular Queue comes to the picture, and we can use circular queue to solve this problem with efficient manner.
Operations on Circular Queue
- Enqueue Operation in Circular Queue:
- Firstly, we have to check whether the queue is full or not
- For the adding first element in the queue, set front to 0
- Increase rear by 1 circularly and add the new element at the position which is pointed by rear
- Dequeue Operation in Circular Queue:
- Firstly, we have to check whether the queue is empty or not.
- Return the element which is pointed by front
- Increase front by 1
- In case of last element of the queue, set values of front and rear to -1
Implementation of Circular Queue
The number of ways implementing the circular queue using:
- Array
- Linked List
Comparison Table
Parameters | Linear Queue | Circular Queue | |
Definition | A linear queue is a linear data structure which works on first in first out concept. We can say a linear queue is homogeneous collection of data items | Circular Queue is special type queue, which follows First in First Out( FIFO) rule and as well as instead of ending queue at the last position, it starts again from the first position after the last position and behaves like circular linear data structure. | |
Insertion and Deletion | In linear queue, we can insert the data item from the end of the queue and deletion can be done from the front of the queue. | In circular queue, we can insert and delete data item from anywhere either front or rear of the queue. | |
Memory space | The linear queue is consumed more memory as compared to the circular queue. | The circular queue is consumed less memory over the linear queue. | |
Utilization of memory | The linear queue is memory inefficient. | The circular queue is memory efficient. | |
Execution order | First in First out principle is followed by the linear queue | No such principle is followed by the circular queue. |