Prerequisite – Circular Singly Linked List
We have discussed basics and how to implement circular queue using array in set 1.
Circular Queue | Set 1 (Introduction and Array Implementation)
In this post another method of circular queue implementation is discussed, using Circular Singly Linked List.
Operations on Circular Queue:
- Front:Get the front item from queue.
- Rear: Get the last item from 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.
- Create a new node dynamically and insert value into it.
- Check if front==NULL, if it is true then front = rear = (newly created node)
- If it is false then rear=(newly created node) and rear node always contains the address of the front node.
- deQueue() This function is used to delete an element from the circular queue. In a queue, the element is always deleted from front position.
- Check whether queue is empty or not means front == NULL.
- 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 = NULL else move the front forward in queue, update address of front in rear node and return the element.
Below is the implementation of above approach:
Elements in Circular Queue are: 14 22 6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 6 Elements in Circular Queue are: 6 9 20
Time Complexity: Time complexity of enQueue(), deQueue() operation is O(1) as there is no loop in any of the operation.
Note: In case of linked list implementation, a queue can be easily implemented without being circular. However, in the case of array implementation, we need a circular queue to save space.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.