Circular Queue
Queues are a fundamental data structure used in various applications for managing data in a
first-in, first-out (FIFO) manner. However, linear queues can lead to inefficient use of
memory, especially when dealing with continuous data streams. This is where circular queues
come in.
Circular queue in data structure provides an efficient way to use available space by wrapping
around when the end of the queue is reached. Here, we will learn what is a circular queue in
data structure, how it works, and how to implement it using an array.
What is Circular Queue?
A circular queue is a special type of queue in data structures where the last position is
connected back to the first position, forming a circle.
This means when the queue reaches the end, it wraps around to the beginning. This helps use
all available space efficiently without leaving any gaps.
For example, if you keep adding items to a circular queue, it will fill up from the start again
after reaching the end. This is useful for tasks like managing waiting lists or buffering data in
a computer system, ensuring no space is wasted.
Circular Queue Operations
Circular queues have several key operations that allow for the efficient management of
elements:
1. Enqueue (Adding an element)
Add an element to the rear of the circular queue.
Steps:
Check if the queue is full. If (rear + 1) % size == front, the queue is full.
If the queue is not full, update the rear pointer to (rear + 1) % size.
Insert the new element at the rear position.
If the queue was initially empty (i.e., front was -1), set front to 0.
2. Dequeue (Removing an element)
Remove an element from the front of the circular queue.
Steps:
Check if the queue is empty. If front == -1, the queue is empty.
If the queue is not empty, remove the element at the front position.
Update the front pointer to (front + 1) % size.
If the queue becomes empty after the dequeue operation (i.e., front equals rear), reset both
front and rear to -1.
3. Peek/Front (Viewing the front element)
View the front element without removing it from the circular queue.
Steps:
Check if the queue is empty. If front == -1, the queue is empty.
If the queue is not empty, return the element at the front position.
4. isEmpty (Checking if the queue is empty)
Check if the circular queue is empty.
Steps:
The queue is empty if front == -1.
isFull (Checking if the queue is full)
Check if the circular queue is full.
Steps:
The queue is full if (rear + 1) % size == front.
How Circular Queue Works?
Advantages of Circular Queue
Efficient Use of Space
Circular queues make efficient use of available space by allowing the rear pointer to wrap
around to the front when the end of the array is reached. This ensures no space is wasted,
unlike in a linear queue where space can be left unused after elements are dequeued.
No Need for Shifting Elements
In a linear queue, when an element is dequeued, all other elements need to be shifted one
position forward to maintain the order. This shifting operation is not required in a circular
queue, as the circular nature takes care of the order, resulting in faster operations.
Fixed Size
Circular queues are implemented using a fixed-size array, which simplifies memory
management. The size of the queue is determined at the time of creation, avoiding the need
for dynamic resizing and memory reallocation.
Consistent Time Complexity
Enqueue and dequeue operations in a circular queue both have a consistent time complexity
of O(1). This means that the time taken for these operations is constant and does not depend
on the number of elements in the queue, leading to predictable performance.
Better Performance in Buffer Management
Circular queues are widely used in buffering scenarios, such as in streaming applications or
operating system task scheduling. They provide a smooth and efficient way to manage
buffers, avoiding buffer overflows and underflows effectively.
Ideal for Resource Management
Circular queues are useful in scenarios where resources need to be managed in a cyclic
manner, such as round-robin scheduling in operating systems. They ensure that each resource
is given equal time and processed in a cyclic order.
Simple Implementation
The logic for implementing circular queues is straightforward and easy to understand. Using
modulo operations to wrap around indices simplifies the code and reduces the potential for
errors.
