Understanding Circular Queue, With Examples

Queues are flexible data structures that are used to simulate numerous real-life situations. They make it practical for us to organize and store data. Queues, however, aren’t always adaptable enough to meet our needs. One way to get around a linear queue’s drawbacks is to use a circular queue. In this post, we’ll examine circular queues’ operation and applications while providing examples.

What is Circular Queue?

The First-In-First-Out (FIFO) principle dictates that the first element added will also be the first to be withdrawn in both circular and regular queues. Circular queues do not, however, have a set beginning or ending point like ordinary lineups do. Instead, the queue is organized in a circular or ring-like fashion, with the back of the line wrapping around to the front. This can be more advantageous than a standard queue, especially when we need cyclical activity, and it improves memory management. This is so that vacant space can be used more easily once some components have been removed without having to change their placements.

What Operations Are Used With Circular Queues?

Circular queues can be used for many of the same processes as a regular queue. For instance, the isEmpty, isFull, and the enqueue, dequeue, and actions. Circular queues do, however, provide extra operations. Here is a quick summary of several frequently used processes.

• 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

It’s time to talk about how circular queues are built now that we’ve covered the fundamental processes. Initializing circular queue arrays or linked lists can be done in two ways. Let’s start with a circular queue based on an array.

Array-based circular queues

It is not difficult to create an array-based circular queue. First, we must initialize the front and rear variables to -1 and the array with a certain size. Then we include elements in the queue. The following steps are used to do this:

By comparing the amount of elements to the queue’s capacity, we first determine whether the queue is full.

The rear pointer is raised by one if there is space in the queue. The rear pointer is wrapped around to the beginning of the queue if it equals the array size.

We determine whether the queue is empty before removing any pieces. The front and rear pointers are compared to accomplish this. In the event that they are equal, the queue is empty.

If the queue is not empty, the front element is removed, and the front pointer is increased by 1. If it reaches the end of the line, it is then coiled around to the beginning.

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, the CircularQueue class is defined. 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.