Home

›

Articles

›

Understanding Circular Queue, With Examples # Understanding Circular Queue, With Examples

Queues are versatile data structures used to model many real-life scenarios. They allow us to store and organize data practically. Sometimes, however, queues aren’t flexible enough for our needs. Using a circular queue is one method for dealing with the limitations of a linear queue. In this article, we’re going to explore how circular queues work and what they’re used for, giving examples.

## What is Circular Queue?

Both regular and circular queues operate on the First-In-First-Out (FIFO) principle, meaning that the first element added will be the first to be removed. Unlike regular queues, however, circular queues do not have a fixed start and end point. Instead, they have a circular or ring-like structure, where the end of the queue wraps around to the front. This can have advantages over an ordinary queue, particularly in situations where we require cyclical behavior, and helps to make memory management more efficient. This is because, after removing elements, the empty space can be utilized easier, without having to adjust the positions of the other elements.

## What Operations Are Used With Circular Queues?

Many operations that are used with a standard queue are also used with circular queues. For example, the enqueue, dequeue, and isEmpty, and isFull operations. But circular queues do have additional operations as well. Here’s a brief overview of operations that are commonly used.

• Enqueue – This is used to insert elements into the queue. Typically, we first check if the queue is full or not, as we can’t add an element to a full queue. If it isn’t full, then we increment the rear pointer to make space for the new element. This pointer then wraps around to the start of the queue.
• Dequeue – This operation is used when we want to delete an element from the queue. First, we must check if the queue is empty. If it’s not empty, then we remove the front element and increment the front pointer. Just as before, this wraps around to the other end of the queue.
• Front and rear – These return the elements at the start and end of the queue respectively, without modifying them.
• IsEmpty and IsFull – These are used to check if the queue is empty or full respectively. While isFull is used with linear queues, it operates differently with circular queues. Instead of checking whether the rear pointer has reached the queue capacity, we compare the number of elements with the capacity.

## Circular Queue – Implementation

Now we’ve covered the basic circular queue operations, it’s time to discuss how they’re implemented. Two main methods are used to initialize a circular queue – arrays or linked lists. Let’s begin with an array-based circular queue.

### Array-based circular queues

The steps to implement an array-based circular queue aren’t too complicated. First, we need to initialize the array with a specific size, as well as initialize the front and rear variables to -1. After this, we add elements to the queue. This is done through the following steps:

First, we check if the queue is full by comparing the number of elements with the queue’s capacity.

If the queue isn’t full, the rear pointer is incremented by 1. If the rear pointer is equal to the array size, it’s wrapped around to the start of the queue.

To remove elements from the queue, we check if it’s empty. This is done by comparing the front and rear pointers. If they’re equal, this means the queue is empty.

If the queue isn’t empty, we remove the front element and increment the front pointer by 1. This is then wrapped around to the end of the queue if it reaches the end of the queue.

To show how this is done, consider the following code in Python:

``````class CircularQueue:
def __init__(self, n):
self.queue = [None] * n
self.capacity = n
self.front = 0
self.rear = -1
self.size = 0

def enqueue(self, item):
if self.isFull():
print("Queue is full. Unable to enqueue.")
return

self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
self.size += 1

def dequeue(self):
if self.isEmpty():
print("Queue is empty. Unable to dequeue.")
return None

front_item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return front_item

def isEmpty(self):
return self.size == 0

def isFull(self):
return self.size == self.capacity

def get_front(self):
if self.isEmpty():
return None
return self.queue[self.front]

def get_rear(self):
if self.isEmpty():
return None
return self.queue[self.rear]

cq = CircularQueue(5)

cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.get_front())
print(cq.get_rear())

item = cq.dequeue()
print(item)

print(cq.get_front())
print(cq.get_rear())``````

### Class declaration

First, we define the “CircularQueue” class. This has the constructor method “def __init__(self, n)” which has parameter “n”, indicating the queue’s capacity. We then create a list of size “n”, and assign the capacity to the “capacity” attribute. We also initialize the front and rear pointers to 0 and -1 respectively, and the size of the list to 0.

### Defining the methods

After this, the “enqueue” method is defined, taking item as a parameter. We also use an if statement to check if the queue is full, printing an appropriate error message if it is. If not, we increment the rear pointer by 1, while using the “%” operator to acknowledge the circular behavior. We then assign the “item” parameter to the position of the rear pointer, which is where the element would be added. Finally, the size of the queue is incremented by 1.

Next, we define the “dequeue” method. The queue is checked to see if it’s empty, printing an error message if this is the case. If it’s not empty, we then remove an element. The first item is retrieved, and the front pointer is incremented by 1. After that, the size of the queue is decremented by 1 to show the removal of the element.

The final methods defined are the “isEmpty” and “isFull” methods. These are true if the queue’s size is 0, or if the capacity is equal to the size.

### Creating the queue

We finish by creating a queue and performing these operations on it. First, we add 3 elements to the queue using enqueue, then print the front and rear elements. After this, we remove the first element and print this element. Finally, the new front and rear elements are printed. The implementation and the results can be seen in the image below.

Since linked lists make use of nodes, adding and removing elements is a slightly different process. To add an element to the queue, we create a new node at the end of the list. We then update the “rear” node so that its “next” attribute points to the new node, and the reference of the new node points to the “front” node.

When removing an element, the “front” node is removed. The “front” reference is then changed to the next node, and the “next” reference of the “rear” node is updated so that it points to the new “front” node.

To see this in action, consider the following code:

``````class Node:
def __init__(self, data):
self.data = data
self.next = None

class CircularQueue:
def __init__(self):
self.front = None
self.rear = None

def enqueue(self, item):
new_node = Node(item)

if self.isEmpty():
self.front = new_node
self.rear = new_node
new_node.next = new_node
else:
new_node.next = self.front
self.rear.next = new_node
self.rear = new_node

def dequeue(self):
if self.isEmpty():
print("Queue is empty. Unable to dequeue.")
return None

front_item = self.front.data

if self.front == self.rear:
self.front = None
self.rear = None
else:
self.front = self.front.next
self.rear.next = self.front

return front_item

def isEmpty(self):
return self.front is None

def get_front(self):
if self.isEmpty():
return None
return self.front.data

def get_rear(self):
if self.isEmpty():
return None
return self.rear.data

cq = CircularQueue()

cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.get_front())
print(cq.get_rear())

item = cq.dequeue()
print(item)

print(cq.get_front())
print(cq.get_rear())``````

### Class declaration

First, we declare the “Node” class and declare the constructor method which takes the “data” value of the node.

We then declare the “CircularQueue” class and another constructor method. This designates an empty queue by initializing the “front” and “rear” pointers to “None”.

### Defining the methods

We then define the “enqueue” method. A new node is created with “item” as a value. We then check if the queue is empty using “isEmpty”, and set the new node to both “front” and “rear”. Its “next” attribute is also set to itself since it’s the only node. Otherwise, if the queue isn’t empty, we set the “next” attribute of the new node to the current front node and the “next” attribute of the rear node to the new node. This links the front and rear of the queue. We also set the new node to the “rear” attribute, so that it’s the new end of the queue.

After this, the “dequeue” method is defined. The status of the queue is checked, and an error message is printed if it’s empty. We then check if there is only one node in the queue, when the front node equals the rear node. If so, then the “front” and “rear” attributes are set to “None”. Otherwise, the front node is updated to the next node, and the “next” attribute of the rear node is set to the new front node so the queue wraps around. The item removed is then printed.

Next, we define the “isEmpty” method. If the front node is “None”, the queue is empty. Then, we define the “get_front” method, which returns the data of the front node. Similarly, we define the “get_rear” method, which returns the data of the rear node.

### Creating the queue

Finally, we create a circular queue as before and add three elements. We print the front and rear nodes, remove an element and print it, then print the front and rear nodes. The output can be seen in the image.

## Wrapping Up

Circular queues have many advantages over linear queues, such as more efficient memory management and the ability to simulate more elaborate queues, such as traffic queues. Although circular queues also operate on the FIFO principle, they don’t have fixed start and end points. If you’re going to be working with queues, understanding how circular queues work is an important part of your learning.

What are circular queues?

Circular queues are used to represent queues, but have no fixed start and end points. The end node wraps around to the front node. This forms a ring-like structure.

What operations are used with circular queues?

The operations are similar to those used with a linear queue – enqueue, dequeue, isEmpty, isFull, front and rear.

How are circular queues implemented?

Circular queues can be implemented using either an array or a linked list.

What are circular queues used for?

Circular queues can be used for memory management, scheduling tasks and CPU operations, as well as real-life scenarios such as queues at traffic lights.

What is the time complexity of circular queue operations?

For enqueue and dequeue operations, the time is constant, and given as O(1).

What are the pros and cons of circular queues?

When using a linked list-based queue, you can dynamically resize the queue easier than with an array. The time complexity of enqueue and dequeue is also constant with a circular queue, whereas they are proportional to the queue size with a linear queue. However, circular queues can still be inefficient if the number of elements is lower than the capacity, and if resizing is frequent. Their usage is also a lot more complex than a linear queue, since maintaining the circular behavior requires more forethought. #### Duncan Dodsworth, Author for History-Computer

Duncan Dodsworth is a writer at History Computer, primarly producing content about personal tech, computers or gaming. Duncan has been writing about tech for over 5 years since he majored in Chemistry in 2016. A resident of London, England, Duncan likes listening to music, playing around with gadgets and reading books half as often as he says he does.