Circular Queue
Let's explain the concept of a circular queue, provide an example with proper comments, and solve a question from LeetCode that involves using a circular queue. We'll also analyze the time and space complexity of our solution.
- Circular Queue: A circular queue is a data structure that follows the FIFO (First-In-First-Out) principle and has a fixed size. It is similar to a regular queue, but the rear and front of the queue are connected to form a circular structure. This allows for efficient use of space and avoids shifting elements when performing enqueue and dequeue operations.
In a circular queue, elements are added at the rear (enqueue) and removed from the front (dequeue). When the rear reaches the end of the queue, it wraps around to the beginning, allowing new elements to be added even if there are empty spaces at the front.
- Example with Comments: Let's demonstrate the implementation of a circular queue with an example. We'll create a circular queue class in Python that supports the enqueue and dequeue operations.
class CircularQueue:
def __init__(self, k):
self.queue = [None] * k
self.size = k
self.front = 0
self.rear = 0
def enqueue(self, value):
# Check if the queue is full
if self.is_full():
return False
# Add the value to the rear
self.queue[self.rear] = value
# Update the rear index
self.rear = (self.rear + 1) % self.size
return True
def dequeue(self):
# Check if the queue is empty
if self.is_empty():
return False
# Remove the value from the front
self.queue[self.front] = None
# Update the front index
self.front = (self.front + 1) % self.size
return True
def front_value(self):
# Get the value at the front
return self.queue[self.front]
def rear_value(self):
# Get the value at the rear
return self.queue[self.rear - 1]
def is_empty(self):
# Check if the queue is empty
return self.front == self.rear and self.queue[self.front] is None
def is_full(self):
# Check if the queue is full
return self.front == self.rear and self.queue[self.front] is not None
# Create a new circular queue with a capacity of 5
cq = CircularQueue(5)
# Enqueue elements
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
# Print the front and rear values
print("Front:", cq.front_value()) # Output: 1
print("Rear:", cq.rear_value()) # Output: 5
# Dequeue elements
cq.dequeue()
cq.dequeue()
# Print the front and rear values
print("Front:", cq.front_value()) # Output: 3
print("Rear:", cq.rear_value()) # Output: 5
In this example, we create a CircularQueue class with the following methods:
enqueue: Adds a value to the rear of the circular queue.dequeue: Removes a value from the front of the circular queue.front_value: Returns the value at the front of the circular queue.rear_value: Returns the value at the rear of the circular queue.is_empty: Checks if the circular queue is empty.is_full: Checks if the circular queue is full.
- Solving a LeetCode Question: Implement Circular Queue Let's solve the LeetCode question "Design Circular Queue," which involves implementing a circular queue with specific requirements. We'll provide a complete code solution with proper comments and explain its time and space complexity.
class MyCircularQueue:
def __init__(self, k: int):
self.queue = [None] * k
self.size = k
self.front = 0
self.rear = 0
def enQueue(self, value: int) -> bool:
# Check if the queue is full
if self.isFull():
return False
# Add the value to the rear
self.queue[self.rear] = value
# Update the rear index
self.rear = (self.rear + 1) % self.size
return True
def deQueue(self) -> bool:
# Check if the queue is empty
if self.isEmpty():
return False
# Remove the value from the front
self.queue[self.front] = None
# Update the front index
self.front = (self.front + 1) % self.size
return True
def Front(self) -> int:
# Get the value at the front
return -1 if self.isEmpty() else self.queue[self.front]
def Rear(self) -> int:
# Get the value at the rear
return -1 if self.isEmpty() else self.queue[(self.rear - 1) % self.size]
def isEmpty(self) -> bool:
# Check if the queue is empty
return self.front == self.rear and self.queue[self.front] is None
def isFull(self) -> bool:
# Check if the queue is full
return self.front == self.rear and self.queue[self.front] is not None
In this solution, we implement the MyCircularQueue class with the same methods as before: enQueue, deQueue, Front, Rear, isEmpty, and isFull. These methods perform the necessary operations on the circular queue and return the expected outputs.
- Time and Space Complexity Analysis:
The time complexity of the
enQueue,deQueue,Front,Rear,isEmpty, andisFullmethods is O(1). These operations involve direct access to the front and rear of the circular queue and simple calculations based on the size.
The space complexity is O(N), where N is the capacity of the circular queue. We use an array of size N to store the elements of the circular queue.
For the LeetCode question "Design Circular Queue," the time complexity is O(1) for all operations, and the space complexity is O(N) due to the array used to store the elements.
By understanding the concept of a circular queue and implementing the necessary methods, we can efficiently solve problems that require the circular queue's functionality, such as managing a fixed-size buffer or processing elements in a circular manner.
Let's solve another LeetCode question that involves using the concept of a circular queue. We'll provide a complete code solution with proper comments and explain its time and space complexity.
Question: "Moving Average from Data Stream"
Problem Description:
Design a class, MovingAverage, which receives a stream of integers and calculates the moving average of all integers in the last N elements.
Implement the MovingAverage class:
MovingAverage(size): Initializes the object with the size of the window.next(val): Returns the moving average of the lastsizevalues of the stream.
Example:
# Create a MovingAverage object with window size 3
m = MovingAverage(3)
# Insert new elements and get the moving average
print(m.next(1)) # Output: 1.0
print(m.next(10)) # Output: 5.5
print(m.next(3)) # Output: 4.666666666666667
print(m.next(5)) # Output: 6.0
class MovingAverage:
def __init__(self, size: int):
self.queue = [0] * size
self.size = size
self.head = 0
self.count = 0
self.sum = 0
def next(self, val: int) -> float:
# If the queue is not yet full, increment the count
if self.count < self.size:
self.count += 1
# Subtract the element at the head from the sum
self.sum -= self.queue[self.head]
# Add the new element to the queue and the sum
self.queue[self.head] = val
self.sum += val
# Move the head to the next index (circularly)
self.head = (self.head + 1) % self.size
# Calculate and return the moving average
return self.sum / self.count
In this solution, we implement the MovingAverage class with two methods:
__init__: Initializes the object with the specified window size. We create a queue of sizesizeusing an array and initialize other variables (head,count, andsum).next: Adds a new value to the stream and returns the moving average. We update the sum by subtracting the element at the head and adding the new value. We also move the head to the next index (circularly) and calculate the moving average.
Time and Space Complexity Analysis:
- The time complexity of the
__init__method is O(1) because it performs constant operations to initialize the object. - The time complexity of the
nextmethod is O(1) because it involves constant operations to update the sum, move the head, and calculate the moving average. - The space complexity is O(N), where N is the window size. We use an array of size N to store the elements of the circular queue.
For the LeetCode question "Moving Average from Data Stream," the time complexity of the next operation is O(1), and the space complexity is O(N), where N is the window size.
By using the concept of a circular queue, we can efficiently calculate the moving average of a stream of integers over a specified window size.