Introduction
Before we understand the concept of Circular Queue, First focus on Queue. Queue is data structure where collection of elements is stored in form of list where items get inserted from one end and deleted from another end.
There are many types of Queue’s like
- Simple Queue
- Circular Queue
- Priority Queue
- Double-Ended Queue (Deque)
Let’s discuss the concept of Circular Queue.
Circular Queue
Circular queue is modified version of Queue data structure, that adheres FIFO principle. It has fixed memory size, due to which it permits better memory utilization compare to simple queue. Main concept of circular queue is that, last element is indexed back to the first element means the last node points to the first node and creates a circular connection. Thus, it allows to insert an item at the first node of the queue when the last node is full and the first node is free.
The feature of indexing last element back to the first create a kind of circle which corelates to ring, thus Circular Queue is also known as ring Buffer Queue.
Need for Circular Queue:
- Circular Queue technique is used in memory management.
- Process Scheduling: CPU schedules process via Queue.
- Circular Queue were employed in traffic system as well.
Operations on Circular Queue:
- Front- get the first item from the queue.
- Rear- get the last item from the queue.
- enqueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.
- Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
- If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.
- deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.
- Check whether queue is Empty means check (front==-1).
- If it is empty then display Queue is empty. If queue is not empty then step 3
- Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.
- isEmpty/isFull- checks if the queue is empty or full.
Enqueue operation
The steps of enqueue operation are given below:
- First, we will check whether the Queue is full or not.
- Initially the front and rear are set to -1. When we insert the first element in a Queue, front and rear both are set to 0.
- When we insert a new element, the rear gets incremented, i.e., rear=rear+1.
Scenarios for inserting an element
There are two scenarios in which queue is not full:
- If rear != max – 1, then rear will be incremented to mod(maxsize) and the new value will be inserted at the rear end of the queue.
- If front != 0 and rear = max – 1, it means that queue is not full, then set the value of rear to 0 and insert the new element there.
There are two cases in which the element cannot be inserted:
- When front ==0 && rear = max-1, which means that front is at the first position of the Queue and rear is at the last position of the Queue.
- front== rear + 1;
Algorithm to insert an element in a circular queue
Step 1: IF (REAR+1)%MAX = FRONT
Write ” OVERFLOW “
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX – 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Dequeue Operation
The steps of dequeue operation are given below:
First, we check whether the Queue is empty or not. If the queue is empty, we cannot perform the dequeue operation.
When the element is deleted, the value of front gets decremented by 1.
If there is only one element left which is to be deleted, then the front and rear are reset to -1.
Algorithm to delete an element from the circular queue
Step 1: IF FRONT = -1
Write ” UNDERFLOW “
Goto Step 4
[END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT
Linear vs. Circular queues
An approach to enqueue an element in queue differentiates the concept of Linear and Circular queue.
A linear queue just adds elements at the end of the queue. Quite similar to a physical queue, however, a linear queue doesn’t move “forward” once an element is dequeued, as this would be quite resource intensive. In Linear queue, allocated memory can’t be reused thus it consumes large memory usage. And also have risk of overwriting important data in memory. Linear queue is comparatively easy to implement.
Whereas, circular queue has fixed buffer memory thus tries to reuse memory usage.
Application of Circular Queue
- Simulating Waiting lines
- Buffers for I/O
- Print Queues
- Keyboard Strokes
- Video Frames
- CPU scheduling.
- Memory management.
