Design Circular Queue Leetcode Problem 622 [Python Solution]

Designing a circular queue is a common problem in data structures and can be a valuable addition to your programming skills.

In this blog post, we'll walk you through the problem, provide a step-by-step solution in Python, explain the reasoning behind our approach, and discuss the time and space complexity of the solution.

By the end of this guide, you'll have a solid understanding of how to implement a circular queue efficiently.

Problem Overview

The problem is as follows:

Design your implementation of the circular queue.

A circular queue is a linear data structure where operations are performed based on the FIFO (First In First Out) principle, and the last position is connected back to the first position to create a circular structure.

It is also known as a "Ring Buffer."

One of the advantages of a circular queue is that it allows us to use the spaces in front of the queue.

In a normal queue, once it becomes full, we cannot insert the next element, even if there is space in front of the queue.

However, with a circular queue, we can use that space to store new values.

You need to implement the MyCircularQueue class with the following methods:

1. MyCircularQueue(k): Initializes the object with the size of the queue, denoted as k.
2. Front(): Returns the front item from the queue.

If the queue is empty, it returns -1.
3. Rear(): Returns the last item from the queue.

If the queue is empty, it returns -1.
4. enQueue(value): Inserts an element into the circular queue.

Returns true if the operation is successful.
5. deQueue(): Deletes an element from the circular queue.

Returns true if the operation is successful.
6. isEmpty(): Checks whether the circular queue is empty or not.
7. isFull(): Checks whether the circular queue is full or not.

You must solve this problem without using the built-in queue data structure in your programming language.

Let's take a closer look at this problem and its constraints.

Understanding the Constraints

Before we dive into the implementation details, it's essential to understand the constraints provided in the problem statement:

• 1 <= k <= 1000: The size of the circular queue can vary from 1 to 1000.
• 0 <= value <= 1000: The values you insert into the circular queue can range from 0 to 1000.
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Now that we have a clear understanding of the problem's requirements and constraints, let's proceed with the solution.

MyCircularQueue LeetCode Problem Solution

To implement the MyCircularQueue class, we'll use a doubly linked list as the underlying data structure.

This approach is intuitive and helps us efficiently perform the required operations.

We'll also provide a Python code solution to the problem.

1. Initialization

The constructor of the MyCircularQueue class takes an integer k as an argument, which represents the maximum capacity of the circular queue.

We also initialize other class variables to maintain the state of the circular queue.

class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k  # Maximum capacity of the circular queue
        self.size = 0  # Current number of elements in the queue
        self.head = self.tail = None  # Pointers for the front and rear of the queue

In the constructor, we set the maximum capacity, initialize the current size to 0, and create two pointers, head and tail, which initially point to None.

These pointers help us manage the front and rear of the circular queue.

2. Enqueue Operation

The enQueue method inserts an element into the circular queue.

If there is enough space in the queue, it returns True; otherwise, it returns False.

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

    node = Node(value)  # Create a new node with the given value

    if self.size == 0:
        self.head = self.tail = node
    else:
        self.tail.next = self.tail = node

    self.size += 1
    return True

Here, we check if the circular queue is full by calling the isFull method.

If it's not full, we create a new node with the given value and insert it into the queue.

If the size is 0, meaning the queue is empty, we set both the head and tail pointers to the new node.

Otherwise, we append the new node to the end of the queue by updating the tail pointer.

3. Dequeue Operation

The deQueue method deletes an element from the front of the circular queue.

If the queue is not empty, it returns True; otherwise, it returns False.

def deQueue(self) -> bool:
    if self.isEmpty():
        return False

    self.head = self.head.next  # Move the head pointer to the next node
    self.size -= 1

    return True

In this method, we check if the circular queue is empty using the isEmpty method.

If it's not empty, we move the head pointer to the next node, effectively removing the front element from the queue.

We also decrement the size of the queue to reflect the removal.

4. Front Operation

The Front method returns the value at the front of the circular queue.

If the queue is empty, it returns -1.

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

Here, we check if the circular queue is empty.

If it's not empty, we return the value stored in the node pointed to by the head pointer.

Otherwise, we return -1.

5. Rear Operation

The Rear method returns the value at the rear of the circular queue.

If the queue is empty, it returns -1.

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

Similar to the Front method, we check if the queue is empty.

If it's not, we return the value stored in the node pointed to by the tail pointer.

If the queue is empty, we return -1.

6. isEmpty Operation

The isEmpty method checks whether the circular queue is empty or not.

def isEmpty(self) -> bool:
    return self.size == 0

This method simply compares the size of the queue to 0. If the size is 0, the queue is empty, and the method returns True.

7. isFull Operation

The isFull method checks whether the circular queue is full or not.

def isFull(self) -> bool:
    return self.size == self.capacity

Here, we compare the size of the queue to its maximum capacity (given as `

self.capacity`).

If the size is equal to the capacity, the queue is full, and the method returns True.

Now that we have defined all the methods, the MyCircularQueue class is ready for use.

Time and Space Complexity Analysis

Let's analyze the time and space complexity of our implementation:

• Time Complexity:

  • enQueue(value): O(1) – Inserting an element at the rear takes constant time.
  • deQueue(): O(1) – Removing an element from the front takes constant time.
  • Front(): O(1) – Accessing the front element takes constant time.
  • Rear(): O(1) – Accessing the rear element takes constant time.
  • isEmpty(): O(1) – Checking if the queue is empty takes constant time.
  • isFull(): O(1) – Checking if the queue is full takes constant time.

• Space Complexity:

  • O(k), where k is the maximum capacity of the circular queue.

We store up to k elements in the queue.

Related Interview Questions By Company:

• Surrounded Regions LeetCode
• Permutations LeetCode
• Find Unique Binary String LeetCode

Related Interview Questions By Difficulty:

• Merge Two Sorted Lists LeetCode
• Reverse Linked List LeetCode
• Reverse Linked List II LeetCode

Related Interview Questions By Category:

• Design Circular Queue LeetCode
• Minimum Window Substring LeetCode
• Wiggle Sort LeetCode

Conclusion

In this blog post, we've walked through the design and implementation of a circular queue in Python, as required by the LeetCode problem 622. We've discussed the methods of the MyCircularQueue class, provided Python code for the solution, and analyzed the time and space complexity.

Implementing data structures like a circular queue is an excellent way to improve your understanding of data structures and algorithms and enhance your programming skills.

This particular problem can also be a valuable exercise in handling front and rear pointers efficiently.