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

### 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).

## Key Differences Between Linear Queue and Circular Queue

- The linear queue is an ordered list in which data elements are organized in the sequential order. In contrast, circular queue stores the data in the circular fashion.
- Linear queue follows the FIFO order for executing the task (the element added in the first position is going to be deleted in the first position). Conversely, in the circular queue, the order of operations performed on an element may change.
- The insertion and deletion of the elements is fixed in linear queue i.e, addition from the rear end and deletion from the front end. On the other hand, the circular queue is capable of inserting and deleting the element from any point until it is unoccupied.
- Linear queue wastes the memory space while circular queue makes the efficient use of space.

#### 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.

## Leave a Reply