🔄 A circular queue Python implementation

Context

I've recently had some fun with a Leetcode problem requiring the reader to implement a circular queue. I found the thought process to solve the problem quite interesting, so I figured I'd share my Python solution here, and try and best explain the reasoning behind it.

What is a circular queue?

It's basically a queue (FIFO) with a fixed size and a ring-like structure, as if its head was connected to its tail. One of the main implications of this structure's behaviour is that when the queue is full, new elements will hence either overwrite the oldest ones, or alternatively not be added to the queue. Here's a small visual helper which helps grasp this logic:

Circular_Queue_Animation

As you can see, one of the benefits of a circular queue is that is has no lost spaces ; When an element is removed from the queue, the space it occupied can instantly be reused by a new incoming element.

Implementation

Alrighty, let's get down to business and go ahead with our implementation. To match the Leetcode problem, we'll implement a circular queue that doesn't overwrite old elements when full, but rather rejects new incoming elements in such cases.

Requirements

Our problem space requires us to implement a circular queue with the following methods:

MyCircularQueue(k) Initializes the object with the size of the queue to be k.
int Front() Gets the front item from the queue. If the queue is empty, return -1.
int Rear() Gets the last item from the queue. If the queue is empty, return -1.
boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
boolean isEmpty() Checks whether the circular queue is empty or not.
boolean isFull() Checks whether the circular queue is full or not.

Execution

We'll start by defining our class and its constructor:


class MyCircularQueue:

    def __init__(self, k: int):
        self.space=k
        self.queue=[None]*k
        self.head=0
        self.tail=-1

We'll need to keep track of the available space in the queue, so we define a space attribute initialized to k, the maximum size of the queue.
We'll also need a list to hold the elements of the queue, which we initialize with None values (could be anything).
Finally, we define two pointers, head and tail, to respectively keep track of the front and rear of our queue. We initialize our head to 0 ,the start of the list, and tail to -1 , indicating that the queue is initially empty.

Let's first implement the isEmpty and isFull methods.


    def isEmpty(self) -> bool:
        return self.space==len(self.queue)

    def isFull(self) -> bool:
        return self.space==0

These two methods are pretty self-explanatory. We can check if our queue is empty by comparing our remaining available space with the size of the queue, and similarly can confirm if it's full by checking if our remaining available space is equal to zero.

Now with the Front and Rear methods. We know that if our queue is empty, we should return -1, so we can already handle this case.


    def Front(self) -> int:
        if self.isEmpty():
            return -1
        ...

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        ...

Now, which values should we return if the queue isn't empty ? Well, we've established that we'd be using head and tail pointers to keep track of the front and rear of the queue, so let's return the values at these respective indices in our queue list.


    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.tail]

And there we go. Now to the meaty parts : the enQueue and deQueue methods.

Let's start with enQueue. We know that if the queue is full, we should return False, so let's handle this case first.


    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        ...

Once we've set this case aside, let's handle our happy path scenario, where we'll want to enqueue this value to our list, meaning we'll want to add this incoming value to the rear of our queue.

To do this, we'll use our tail pointer that tracks the rear of the queue. We'll first make it point to the next available space in the queue, to not overwrite the current element at the end of the queue. Then, we can safely set the value at that index to the incoming value. Finally, we'll decrement our available space by 1, and return True to indicate that the operation was successful.

def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.tail=self.tail+1
        self.queue[self.tail]=value
        self.space-=1
        return True

But wait a minute, what if our tail pointer goes out of bounds of our list ? How should we handle this case, and more generally the circular nature of our queue ?

Here's where the circular logic comes into play. When our tail pointer reaches the end of our list, we actually want it to wrap around and point back to the start of the list. To achieve this, we can use the modulo operator % to ensure that our tail pointer always stays within the bounds of our list : every time we'll increment our tail pointer, we'll take its value modulo the length of the queue.

def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.tail=(self.tail+1)%len(self.queue)
        self.queue[self.tail]=value
        self.space-=1
        return True

We are now sure that our tail pointer will always stay within the bounds of our list, effectively creating a circular behaviour.

In our case, we furthermore know for sure that no overwriting will happen, since we already checked that the queue isn't full at the start of our method : this means that there are some empty spaces in our queue array structure, in which we can safely add our new value (either at the end or at the beginning when the tail wraps around).

In a very similar fashion, here's the deQueue method.

def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.queue[self.head]=None ## Optional, just to make it clear that this space is now empty
        self.head=(self.head+1)%len(self.queue)
        self.space+=1
        return True

To be noted that in the dequeue case, we increment the head pointer to point to the next element in the queue after removing the front element.

There we have it, our complete implementation of a circular queue in Python !

Full code below for clarity:


class MyCircularQueue:

    def __init__(self, k: int):
        self.space=k
        self.queue=[None]*k
        self.head=0
        self.tail=-1

    def isEmpty(self) -> bool:
        return self.space==len(self.queue)

    def isFull(self) -> bool:
        return self.space==0

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.tail]

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.tail=(self.tail+1)%len(self.queue)
        self.queue[self.tail]=value
        self.space-=1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.queue[self.head]=None ## Optional, just to make it clear that this space is now empty
        self.head=(self.head+1)%len(self.queue)
        self.space+=1
        return True

And that's it for today folks, hope you enjoyed this little read as much as I enjoyed writing it. See you next time !