Linear Queue VS Circular Queue

What is Queue?

A queue is one of the important linear data structures extensively used in various computer applications. It is based on the FIFO (First In First Out) principle. It follows a particular order of execution of data for which operations are performed.  In this data structure, data enters from one end, i.e., REAR end, and next data enters in the queue after the previous one, and deletion operation is performed from another end, .i.e., FRONT end.

As compare with stacks, stacks are also a linear data structure. Although, it is based on LIFO (Last In First Out) principle, which implies that data enters one by one from one end into the stack till it reaches its end limit, and it popped out the data element from the stack from that end itself.

In a stack, only one pointer is needed for performing all operations, which is top, whereas, in the queue, there are two pointers needed, rear and front, for performing all operations.

Types of Queues

The types of queue are as follows:

• Linear Queue
• Circular Queue
• Deque
• Priority Queue
• Multiple Queue

Linear queue

A linear queue is said to be the simple queue, and whenever we need to talk about the queue, it is by default set that we are considering a linear queue. A linear queue is a linear data structure based on FIFO (First In First Out) principle, in which data enters from the rear end and is deleted from the front end. We will discuss these ends in more detail further.  

With an example of the Movie Ticket counter, a customer comes first in the queue is served first, and the next customer to that one comes after. This process will continue till all the tickets for that movie have been booked.

Other examples includes:

• People are waiting for the bus. The first person up standing in the queue will be the first to get on the bus.
• Cars lined at a toll bridge. The first car to reach out the bridge will be the first to leave.

Operations performed on Linear Queue

There are certain basic operations has performed in the linear queue are as follows->

1. Enqueue

• For the addition of data elements in the queue, this operation is used.
• By applying this operation, data is entered in the queue according to the sequence after one another. En queue will be continued till the queue reaches its end limit.
• After it reaches the endpoint, the data cannot add to the queue, and then such condition is said to be an Overflow condition.
• En-queue operation is done from the rear end.

2. Dequeue

• For deletion of a data element from the queue, this operation is used.
• By Using this operation, that data element is deleted, which is enqueued first in the queue, or the elements are popped in the same order in which they are pushed in the queue.
• This process will delete the data elements from the queue until the whole queue becomes empty. Once all the elements are deleted, then the deletion operation is unable to execute, and then such condition is said to be an Underflow condition.
• It is done from the front end.

3. Peek

 This operation is used to find out the very first queue element, which is to be served first without dequeuing it.

Two Ends of Linear Queue

1. Front end- It refers to the initial or starts position of the queue. The front end is mainly used to delete the data element from the queue or perform a de queue operation.
2. Rear end- It refers to the last or back position of the queue. The rear end is mainly used to insert the data elements in the queue or to perform the en-queue operation.

Methods of Implementation of Linear queue

There are various methods of implementation of the queue:

• Queue implementation using an array
• Queue implementation using stack
• Queue implementation using linked list

Implementation of Linear queue using an Array

Here we discuss the implementation of queue using an array->

Queues can easily be implemented by using linear arrays. As stated earlier, the queue has front and rear pointers that point to the position where deletion and insertion of data elements can be done.

Steps

1. Initially, we need to create an array of size 'n' whether statically or dynamically depends on the user.
2. Then declare two pointers named FRONT and REAR.
3. Initialize REAR = -1 and FRONT = 0.
4. Create three functions named Enqueue for adding data elements in the queue, Dequeue for deletion of a data element from the queue, and peek for finding out the first element from the queue without dequeuing it.

                                 Implementation of linear queue

Algorithms

Algorithms of Enqueue operation

Step 1- Check if REAR == FRONT.

Step 2- If the above statement holds, then such a condition is said to be an Overflow, and further insertion of data elements is not possible.

Step 3- If it holds false, then

• set REAR = REAR + 1 and
• Add the data element in queue at rear position. 
• Queue[REAR] = data.

Algorithm of Dequeue operation

Step 1- Check if FRONT = REAR + 1

Step 2- If the above statement holds, then

• Such condition is said to be Underflow condition.
• Return -1.

Step 3- If it holds false, then

• popped out the value from the queue present at the front position
• Data = Queue[FRONT].
• Return data.

     Step 4-> Set FRONT = FRONT + 1, it points next data element.

Algorithm of Peek operation

Step 1- Check if FRONT = REAR + 1.

Step 2- If the above statement holds, then display the message; the queue is empty.

Step 3- If it holds false,

• Return the data element from the queue present at the front position.
• Data = Queue[FRONT].
• Return data.

Circular Queue

A circular queue is also one of the important types of a queue. It is similar to the linear queue but has some variations. The end position of a circular queue is connected back to the start position, forming the circular-like structure and making a circle. A circular queue is also based on the First In First Out (FIFO) principle. It is also known as 'Ring Buffer'.

As we have seen previously, in a linear queue, further insertion of data elements is not possible when REAR reaches the end, and FRONT also reaches to end. The queue is still empty, but it shows that the queue is full, so to overcome the above problem concept of circular is introduced. In the circular queue, this problem will not arise. We will further discuss it in more detail in the below section.

                                            Circular queue

Applications of Circular queue

• Round Robin scheduling is one of the major applications of the circular queue. This algorithm is employed by process and network schedulers in computing.

• It is also used in computer-controlled Traffic Signal Systems.

• It is also used in CPU scheduling and memory management.

Operations performed on Circular queue

There are certain basic operations has performed in the linear queue are as follows->

1. Enqueue

• This operation is used for the insertion of a data element in the queue.
• In a circular queue, the addition of a data element is always done from the rear position.

2. Dequeue

• This operation is used for the removal of a data element from the queue.
• In a circular queue, deletion of a data element is always done from the front position.

Two ends of Circular queue

In a circular queue, there is a circle like structure; hence there are no two ends distinguished but still, to differentiate the insertion and deletion criteria of data elements, we refer to these two ends:

1. Front end-> it is used to delete the data elements from the queue.
2. Rear end-> it is used to insert the data elements in the queue.

Implementation of Circular queue using an array

A circular queue can easily be implemented using arrays. It works on the circular increment process. As stated earlier, it has two pointers, front, and rear. From the rear end, insertion of data elements is possible. If the rear pointer reaches the end, it again increments back to the initial position of the queue so that further insertions can also be possible; hence this implies an increment process.

From the front end, deletion of data elements is possible. If the front pointer reaches to end, it returns to the queue's initial position so that further deletions can be possible.   

By using modulo division with the queue size, the circular increment is performed.

Steps

1. Initially, we need to create an array of size 'n' whether statically or dynamically depends on the user.
2. Then declare two pointers named FRONT and REAR.
3. Initialize REAR = -1 and FRONT = -1.
4. Create two functions named Enqueue for adding data elements in the queue,  Dequeue for the deletion of data elements from the queue.

                                 Implementation of Circular queue

Algorithm of Enqueue operation

Step 1-> Check if FRONT == 0 && REAR == (n-1) || REAR == (FRONT – 1) % (n-1).

Step 2- If the above statement holds, then such condition is said to be an Overflow, and further insertion of data elements is not possible.

Step 3- Else if FRONT == -1 then,

• set REAR = 0, FRONT = 0 and
• Add the data element in queue at rear position. 
• Queue[REAR] = data.

Step 4- Else if REAR == (n-1) &&  FRONT != 0

• set REAR = 0 and
• Add the data element in queue at rear position. 
• Queue[REAR] = data.

      Step 5- Else

• set REAR = REAR + 1
• Add the data element in queue at rear position. 
• Queue[REAR] = data.

Algorithm of Dequeue operation

     Step 1-Check if FRONT == -1

Step 2- If the above statement holds, then

• Such condition is said to be an Underflow condition.
• Return -1.

     Step 3- If it holds false, then

• popped out value from the queue present at the front position
• Data = Queue[FRONT].
• Return data.

     Step 4- Set FRONT = FRONT + 1, it points next data element.

      Step 5-If FRONT == REAR then, set FRONT = -1 and REAR = -1.

     Step 6-> Else if FRONT == n-1 then, set FRONT = 0.

Advantages of Circular queue over Linear queue->

• Linear queue consumes more memory as compared to circular queue.
• A circular queue uses an efficient way for memory utilization.
• In a circular queue, new data can be inserted again at a particular position after deleting previous data on that position.
• In a linear queue, if the rear pointer reaches last and the front pointer deletes all data from the queue, it remains to show the message of Overflow, which is the main drawback of the linear queue.
•  In a circular queue, an overflow message is shown when the queue is full.
• Easy to perform dequeue operation and enqueue operation.

On the basis of comparison	Linear Queue	Circular queue
Arrangement	It arranges data in linear order.	It arranges data in circular order.
Definition	It is a linear data structure that contains the data in linear sequential order. Here rear end is not connected with the front end.	It is also a linear data structure in which the rear end is connected with the front end.
Insertion and Deletion operation	Insertion is done from the rear end, whereas deletion is done from the front end. Hence here it is fixed.	Due to a circular structure, we can not distinguish the exact position of insertion and deletion. Hence here, it is not fixed.
Peek operation	In a linear queue, we can easily fetch out the peek value.	As it is circularly arranged, we cannot fetch out the peek value.
Memory space	It requires more memory space.	It requires less memory space.
Utilization of memory	In a linear queue, there is an inefficient way of the utilization of memory.	In a circular queue, there is an efficient way of the utilization of memory.