What is circular queue? What are in advantage? Write the algorithm for insertion and deletion operation performed by circular queue.
Answer: – A simple or in a straight line queue there are severed limitations we known, even if memory locations at the beginning of queue are available elements can’t be inserted. We can efficiently utilize the space available of straight line queues by using circular queue.
In the circular queue, the first element is stored immediately after the last element. If last location of the queue is occupied, the new element is inserted at the first memory location of queue implementing an array for example, C[n], C is queue of n an element after inserting, storing an element in the last memory location [(n-1th) element], the next will be stored at the first location, if space is available it is like a chain of where starting and ending points are joined and a circle is formed When an element is stored in the last location wrapping taken place and element inserting routine of the program pointed to beginning of the queue.
Recall that a pointe plays an important role to know the position of the elements in the stack and queue. There, as soon as last element is filled, the pointer is wrapped to the beginning of the queue by shifting the pointer value to one.
A circular queue overcomes the limitation of the simple queue by utilizing the entire space of the queue. Like a simple queue, the circular queue also have front and rear ends. The rear ends and front ends help us to know the status of the queue after the insertion and deletion operation. In the circular queue implementation, the element shifting operation of queue that that we apply in the simply queue is not required. The pointer itself takes care to move at vacant location of the queue and element is placed at that location. In order to simulate the circular queue a programmer should follow the following points.
- The front end of the queue always points to the first element of the queue.
- If the value of front and queue are equal, the queue is empty. The values of front and rear pointers are only increased / decreased after insertion / deletion operation.
- Like simple queue, rear pointer’s is incremented by one when new element is inserted and front pointer is incremented by one when. Element is deleted.
Algorithm for insertion in queue: –
Step 1: [Check overflow condition] If rear≥ size Output “over flow” and return Step 2: [Increment rear pointer] Rear=rear+1 Step 3: [Insert an element] Q[rear]=value Step 4: [Set the front pointer] If front=0 Front=1 Step 5: Return
Algorithm for deletion in queue: –
Step 1: [Check underflow condition] If front=0 Output “underflow” and returns Step 2: [Remove an element] Value=Q[front] Step 3: [Check for empty queue] If front =rear Front=0 Rear=0 Else Front=front+1 Step 4: Return (Value)