Difference Between Linear Queue and Circular Queue

A simple linear queue can be implemented in various three ways, among which one of the types is a circular queue. The difference between linear and circular queue lies in the structural and performance factors. The essential difference between the linear queue and the circular queue is that the linear queue consumes more space than the circular queue, while the circular queue was devised to limit the memory wastage of the linear queue.

The queue can be described as non-primitive linear data structure follows the FIFO order in which data elements are inserted from the one end (rear end) and deleted from the other end (front end). The other variations of the queue are the circular queue, doubly ended queue and priority queue.

Content: Linear Queue Vs Circular Queue

1. 1. Comparison Chart
   2. Definition
   3. Key Differences
   4. Implementation
   5. Conclusion

Comparison Chart

Basis for comparison	Linear Queue	Circular Queue
Basic	Organizes the data elements and instructions in a sequential order one after the other.	Arranges the data in the circular pattern where the last element is connected to the first element.
Order of task execution	Tasks are executed in order they were placed before (FIFO).	Order of executing a task may change.
Insertion and deletion	The new element is added from the rear end and removed from the front.	Insertion and deletion can be done at any position.
Performance	Inefficient	Works better than the linear queue.

Definition of Linear Queue

A Linear queue is rationally a first in first out ordered list. It is so called linear because it resembles to a straight line where the elements are positioned one after the other. It contains a homogeneous collection of the elements in which new elements are added at one end and deleted from another end. The concept of the queue can be understood by the example of a queue of the audience waiting outside the ticket counter to get the theatre ticket. In this queue, the person joins the rear end of the queue to take the ticket and the ticket is issued at the front end of the queue.

There are several operations performed in the queue

• Firstly the queue is initialized to zero (i.e. empty).
• Determine whether the queue is empty or not.
• Determine if the queue is full or not.
• Insertion of the new element from the rear end (Enqueue).
• Deletion of the element from the front end (Dequeue).

The queue can be implemented in two manners

• Statically (Using arrays)
• Dynamically (Using pointers)

The limitation of the linear queue is that it creates a scenario where no new element can be added in the queue even if the queue contains the empty spaces. This above situation is illustrated in the figure given below. Here the rear is pointing to the last index while all the boxes are empty still, no new element can be added.

Definition of Circular Queue

A circular queue is a variant of the linear queue which effectively overcomes the limitation of the linear queue. In circular queue, the new element is added at the very first position of the queue if the last is occupied and space is available. When it comes to linear queue the insertion can be performed only from the rear end and deletion from the front end. In a full queue after performing series of successive deletions in the queue arises a certain situation where no new element can be added further even if the space available because the underflow condition (Rear = max – 1) still exists.

Circular queue connects the two ends through a pointer where the very first element comes after the last element. It also keeps track of the front and rear by implementing some extra logic so that it could trace the elements that are to be inserted and deleted. With this, the circular queue does not generate the overflow condition until the queue is full in actual.

Some conditions followed by the circular queue:

• Front must point to the first element.
• The queue will be empty if Front = Rear.
• When a new element is added the queue is incremented by value one(Rear = Rear + 1).
• When an element is deleted from the queue the front is incremented by one (Front = Front + 1).

Implementation of the linear queue

The algorithm given below illustrates the addition of elements in a queue:
The queue needs three data variables including one array to store the queue and other to store the front and rear initial position that is -1.

insert (item, queue, n, rear)
{
if (rear == n)
then print "queue overflow";
else
{
rear = rear + 1;
queue [rear] = item;
}
}

The algorithm given below illustrates the deletion of elements in a queue:

delete_circular (item, queue, rear, front)
{
if (rear == front)
then print "queue underflow";
else
{
front = front + 1;
item = queue [front];
}
}

Implementation of the circular queue

An algorithm to interpret the addition of the element in the circular queue:

insert_circular (item, queue, rear, front)
{
rear = (rear+1) mod n;
if (front == rear)
then print "queue is full";
else
{
queue [rear] = item ;
}
}

Algorithm explains the deletion of the element in the circular queue:

delete_circular (item, queue, rear, front)
{
if (front == rear)
then print ("queue is empty");
else
{
front = front + 1;
item = queue [front];
}
}

Conclusion

The linear queue is inefficient in certain cases where the elements are required to shift to the vacant spaces in order to perform insertion operation. That is the reason it tends to waste the storage space while circular queue makes appropriate use of storage space as the elements are added at any position if there exists an empty space.