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.

Linked list-based circular queues

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.

The image featured at the top of this post is ©metamorworks/Shutterstock.com.