Circular Queue is a linear data structure that follows the First-In-First-Out (FIFO) order like the Linear Queue. Additionally, the last position is connected back to the first position to form the circle. This solves the problem of the Linear Queue to use the memory space effectively.
Representation
- Front: Front side of the Queue
- Rear: Rear side of the Queue
- Element: The actual data (represented as 10, 20, 30, 40, 50, and 60)
- Circular: The first and last position is connected to form the circle.
Circular Queue Operations and Time Complexity
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Enqueue | Insert a new element on the Rear | O(1) | O(n) |
| Dequeue | Delete the element from the Front | O(1) | O(n) |
| Peek | Returns the front element without removing | O(1) | O(n) |
| IsFull | Check if the Queue is full | O(1) | O(n) |
| IsEmpty | Check if the Queue is empty | O(1) | O(n) |
| Search | Search the element by value | O(n) | O(n) |
Implementations of Circular Queue
Circular Queues can be implemented using Array or Linked List. However, we must choose the correct implementation based on the requirements.
- Prefer Circular Queue Implementation using Array to work with a fixed amount of data.
- Prefer Circular Queue Implementation using Linked List to work with large and dynamic data.
Advantages and Disadvantages
Advantages
- Memory space is effectively used in Array implementation.
- The linked list implementation can traverse the whole list starting from any node.
Disadvantages
- We must keep track of the last position and switch the Front/Rear pointers to the first position.
Applications of Circular Queue
When to use circular queues?
Prefer circular queues when you choose to implement the Queue using an array. Because, in linear form, the array memory is not effectively utilized. The elements are dequeued from the Front side, but the empty spaces are unused.
In Circular Queues, the empty spaces at the front are utilized since the Rear can circle to the beginning. The new elements are inserted at the beginning of the Array.
Realtime Applications
- Traffic system to switch on the traffic lights in a circular fashion based on the time slot.
- Operating systems often maintain the Queue of processes for CPU scheduling.