Prerequisites

To learn about Circular Queue, you should first have a good understanding of the following:

1. Python 3
2. Linear Queues (you can learn more here)
3. Basic Python data structure concepts - lists
4. Basic math operations - modulo(%)

What is a Circular Queue?

Before you go ahead and read this tutorial, I highly recommend you to read our previous tutorial on Queues as we will be building off of those concepts. Circular Queues are widely used and are often tested on job interviews. A Circular Queue can be seen as an improvement over the Linear Queue because: fake rolex cellini

1. There is no need to reset Head and Tail pointers since they reset themselves. This means that once the Head or Tail reaches the end of the Queue, it resets itself to 0.
2. The Tail and Head can point to the same location - this means the Queue is empty
3. The Head can be greater than the Tail or vice-versa. This is possible because the Head and Tail pointers are allowed to cross each other.

Check out this animation to understand the circular queue a bit better.

Observations based on the above animation:

1. Head pointer - Points to the front of the Queue. Or in other words, it points to the element to be removed if the dequeue operation is called.
2. Tail pointer - Points to the next empty spot in which the new element can be inserted. In the above animation, if you tried to fill the queue completely you wouldn't be able to enqueue after the 13th position. This is because the Tail has no empty spot to point to after an element is inserted in the 14th position. The queue is considered full, even though there is one empty spot left. You should also try doing three or four dequeue operations and then enqueueing an element. Here you will observe that the elements are inserted from the 14th position and then it restarts from 0. It is for this reason that it is called a circular queue.
3. Number of elements:
   1. Tail>=Head: Number of elements = Tail - Head. For instance, if Head = 2 and Tail = 5, then the number of elements will be 5 - 2 = 3
   2. Head>Tail: Number of elements = (Size of Queue) - (Head-Tail) =  (Size of Queue) - Head + Tail. For instance, Head = 14, Tail = 5 and Size of Queue = 15, then the number of elements = 15 - (14 - 5) = 6

How to implement circular queue?

I hope you now feel confident that you know what a circular queue is. Let's see how to implement it using the language agnostic method. To do this, we need to treat Lists like arrays, hence we will restrict its size.

Note: During a dequeue operation, the Head pointer will be incremented by 1 but no element will actually be removed from the queue. This is because once an element is removed, the list automatically shifts all the other elements by one position to the left. This means that the position 0 will always contain an element which is not how an actual queue/circular queue works.

Algorithm

The following steps can be seen as a flow chart to the operation of the Circular Queue:

1. Initialize the queue, size of the queue (maxSize), head and tail pointers
2. Enqueue:
   1. Check if the number of elements (size) is equal to the size of the queue (maxSize):
      1. If yes, throw error message "Queue Full!"
      2. If no, append the new element and increment the tail pointer
3. Dequeue:
   1. Check if the number of elements (size) is equal to 0:
      1. If yes, throw error message "Queue Empty!"
      2. If no, increment head pointer
4. Size:
   1. If tail>=head, size = tail - head
   2. if head>tail, size = maxSize - (head - tail)

Note: The range for the head and tail pointer should be between 0 and maxSize - 1,  hence we are using the logic that if we divide x by 5, then the remainder can never be greater than 5. In other words, it should be between 0 and 4. So apply this logic to the formulae tail = (tail+1)%maxSize and head = (head+1)%maxSize. Observe that this is helps us to avoid reinitializing tail and head to 0 when the queue becomes full.

Program

class CircularQueue:

    #Constructor
    def __init__(self):
        self.queue = list()
        self.head = 0
        self.tail = 0
        self.maxSize = 8

    #Adding elements to the queue
    def enqueue(self,data):
        if self.size() == self.maxSize-1:
            return ("Queue Full!")
        self.queue.append(data)
        self.tail = (self.tail + 1) % self.maxSize
        return True

    #Removing elements from the queue
    def dequeue(self):
        if self.size()==0:
            return ("Queue Empty!") 
        data = self.queue[self.head]
        self.head = (self.head + 1) % self.maxSize
        return data

    #Calculating the size of the queue
    def size(self):
        if self.tail>=self.head:
            return (self.tail-self.head)
        return (self.maxSize - (self.head-self.tail))

q = CircularQueue()
print(q.enqueue(1))
print(q.enqueue(2))
print(q.enqueue(3))
print(q.enqueue(4))
print(q.enqueue(5))
print(q.enqueue(6))
print(q.enqueue(7))
print(q.enqueue(8))
print(q.enqueue(9))
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

Application

There are several uses for Circular Queues, such as:

1. Computer Architecture (Scheduler)
2. Disk drivers
3. Video buffering
4. Printer job scheduling

Conclusion

Circular Queue may appear a little confusing at first but the only way to get the hang of it is to keep practicing. Try out different enqueue and dequeue operations in the animation link provided above to see how it works. That’s it for this tutorial. Happy Pythoning!